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 {
22namespace tidy::bugprone {
23
24namespace {
25/// matches a Decl if it has a "no return" attribute of any kind
26AST_MATCHER(Decl, declHasNoReturnAttr) {
27 return Node.hasAttr<NoReturnAttr>() || Node.hasAttr<CXX11NoReturnAttr>() ||
28 Node.hasAttr<C11NoReturnAttr>();
29}
30
31/// matches a FunctionType if the type includes the GNU no return attribute
32AST_MATCHER(FunctionType, typeHasNoReturnAttr) {
33 return Node.getNoReturnAttr();
34}
35} // namespace
36
37static Matcher<Stmt> loopEndingStmt(Matcher<Stmt> Internal) {
38 Matcher<QualType> IsNoReturnFunType =
39 ignoringParens(InnerMatcher: functionType(typeHasNoReturnAttr()));
40 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, ObjCIvarRefExpr, ObjCPropertyRefExpr,
87 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(InnerMatcher: expr(forCallable(InnerMatcher: decl().bind(ID: "func"))).bind(ID: "condition")),
278 unless(hasBody(InnerMatcher: hasDescendant(
279 loopEndingStmt(Internal: forCallable(InnerMatcher: equalsBoundNode(ID: "func")))))));
280
281 Finder->addMatcher(NodeMatch: mapAnyOf(whileStmt, doStmt, forStmt)
282 .with(LoopCondition)
283 .bind(ID: "loop-stmt"),
284 Action: this);
285}
286
287void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
288 const auto *Cond = Result.Nodes.getNodeAs<Expr>(ID: "condition");
289 const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>(ID: "loop-stmt");
290 const auto *Func = Result.Nodes.getNodeAs<Decl>(ID: "func");
291
292 if (isKnownToHaveValue(Cond: *Cond, Ctx: *Result.Context, ExpectedValue: false))
293 return;
294
295 bool ShouldHaveConditionVariables = true;
296 if (const auto *While = dyn_cast<WhileStmt>(Val: LoopStmt)) {
297 if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
298 if (const Expr *Init = LoopVarDecl->getInit()) {
299 ShouldHaveConditionVariables = false;
300 Cond = Init;
301 }
302 }
303 }
304
305 if (ExprMutationAnalyzer::isUnevaluated(Stm: LoopStmt, Context&: *Result.Context))
306 return;
307
308 if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
309 return;
310 if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func,
311 Ctx: Result.Context))
312 return;
313
314 std::string CondVarNames = getCondVarNames(Cond);
315 if (ShouldHaveConditionVariables && CondVarNames.empty())
316 return;
317
318 if (CondVarNames.empty()) {
319 diag(Loc: LoopStmt->getBeginLoc(),
320 Description: "this loop is infinite; it does not check any variables in the"
321 " condition");
322 } else {
323 diag(Loc: LoopStmt->getBeginLoc(),
324 Description: "this loop is infinite; none of its condition variables (%0)"
325 " are updated in the loop body")
326 << CondVarNames;
327 }
328}
329
330} // namespace tidy::bugprone
331} // namespace clang
332

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