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;
19using clang::tidy::utils::hasPtrOrReferenceInFunc;
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(InnerMatcher: functionType(typeHasNoReturnAttr()));
40 internal::Matcher<Decl> isNoReturnDecl =
41 anyOf(declHasNoReturnAttr(), functionDecl(hasType(InnerMatcher: isNoReturnFunType)),
42 varDecl(hasType(InnerMatcher: blockPointerType(pointee(isNoReturnFunType)))));
43
44 return stmt(anyOf(
45 mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),
46 callExpr(Internal,
47 callee(InnerMatcher: mapAnyOf(functionDecl, /* block callee */ varDecl)
48 .with(isNoReturnDecl))),
49 objcMessageExpr(Internal, callee(InnerMatcher: 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>(Val: 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>(Val: Cond)) {
72 if (const auto *Var = dyn_cast<VarDecl>(Val: 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>(Val: Cond)) {
88 // FIXME: Handle MemberExpr.
89 return true;
90 } else if (const auto *CE = dyn_cast<CastExpr>(Val: 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, Cond: 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>(Val: Cond)) {
125 if (const auto *Var = dyn_cast<VarDecl>(Val: 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(Cond: 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>(Val: &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(Cond: *BinOp->getLHS(), Ctx, ExpectedValue: false) ||
150 isKnownToHaveValue(Cond: *BinOp->getRHS(), Ctx, ExpectedValue: false);
151 if (ExpectedValue && BinOp->getOpcode() == BO_LOr)
152 return isKnownToHaveValue(Cond: *BinOp->getLHS(), Ctx, ExpectedValue: true) ||
153 isKnownToHaveValue(Cond: *BinOp->getRHS(), Ctx, ExpectedValue: true);
154 if (BinOp->getOpcode() == BO_Comma)
155 return isKnownToHaveValue(Cond: *BinOp->getRHS(), Ctx, ExpectedValue);
156 } else if (const auto *UnOp = dyn_cast<UnaryOperator>(Val: &Cond)) {
157 if (UnOp->getOpcode() == UO_LNot)
158 return isKnownToHaveValue(Cond: *UnOp->getSubExpr(), Ctx, ExpectedValue: !ExpectedValue);
159 } else if (const auto *Paren = dyn_cast<ParenExpr>(Val: &Cond))
160 return isKnownToHaveValue(Cond: *Paren->getSubExpr(), Ctx, ExpectedValue);
161 else if (const auto *ImplCast = dyn_cast<ImplicitCastExpr>(Val: &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>(Val: StmtNode)) {
179 const Decl *Callee = Call->getDirectCallee();
180
181 if (!Callee)
182 return false; // unresolved call
183 Callees.insert(Ptr: Callee->getCanonicalDecl());
184 }
185 if (const auto *Call = dyn_cast<ObjCMessageExpr>(Val: StmtNode)) {
186 const Decl *Callee = Call->getMethodDecl();
187
188 if (!Callee)
189 return false; // unresolved call
190 Callees.insert(Ptr: Callee->getCanonicalDecl());
191 }
192 for (const Stmt *Child : StmtNode->children())
193 if (Child && !populateCallees(StmtNode: 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(Ptr: 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>(Val: Cond))
219 if (const auto *VD = dyn_cast<VarDecl>(Val: DRE->getDecl()))
220 if (VD->isStaticLocal())
221 return true;
222 for (const Stmt *Child : Cond->children())
223 if (Child && hasStaticLocalVariable(Cond: 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(StmtNode: LoopStmt, Callees&: 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(G: &CG),
263 SCCE = llvm::scc_end(G: &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(SCC: *SCCI, Callees: CalleesInLoop, Func: Func->getCanonicalDecl()))
270 return true;
271 }
272 return false;
273}
274
275void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
276 const auto LoopCondition = allOf(
277 hasCondition(
278 InnerMatcher: expr(forCallable(InnerMatcher: decl().bind(ID: "func"))).bind(ID: "condition")),
279 unless(hasBody(InnerMatcher: hasDescendant(
280 loopEndingStmt(Internal: forCallable(InnerMatcher: equalsBoundNode(ID: "func")))))));
281
282 Finder->addMatcher(NodeMatch: mapAnyOf(whileStmt, doStmt, forStmt)
283 .with(LoopCondition)
284 .bind(ID: "loop-stmt"),
285 Action: this);
286}
287
288void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
289 const auto *Cond = Result.Nodes.getNodeAs<Expr>(ID: "condition");
290 const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>(ID: "loop-stmt");
291 const auto *Func = Result.Nodes.getNodeAs<Decl>(ID: "func");
292
293 if (isKnownToHaveValue(Cond: *Cond, Ctx: *Result.Context, ExpectedValue: false))
294 return;
295
296 bool ShouldHaveConditionVariables = true;
297 if (const auto *While = dyn_cast<WhileStmt>(Val: 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(Smt: LoopStmt, Stm: *LoopStmt, Context&: *Result.Context))
307 return;
308
309 if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
310 return;
311 if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func,
312 Ctx: 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(Loc: LoopStmt->getBeginLoc(),
321 Description: "this loop is infinite; it does not check any variables in the"
322 " condition");
323 } else {
324 diag(Loc: LoopStmt->getBeginLoc(),
325 Description: "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
333

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