xref: /llvm-project/clang-tools-extra/clang-tidy/bugprone/InfiniteLoopCheck.cpp (revision 63dfe70b224b562f4e5a4e8367353127684584df) 
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 
17 using namespace clang::ast_matchers;
18 using clang::ast_matchers::internal::Matcher;
19 using clang::tidy::utils::hasPtrOrReferenceInFunc;
20 
21 namespace clang {
22 namespace tidy::bugprone {
23 
24 namespace {
25 /// matches a Decl if it has a  "no return" attribute of any kind
26 AST_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
32 AST_MATCHER(FunctionType, typeHasNoReturnAttr) {
33   return Node.getNoReturnAttr();
34 }
35 } // namespace
36 
37 static Matcher<Stmt> loopEndingStmt(Matcher<Stmt> Internal) {
38   Matcher<QualType> IsNoReturnFunType =
39       ignoringParens(functionType(typeHasNoReturnAttr()));
40   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`.
53 static 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`.
69 static 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`.
107 static 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`.
123 static 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 
142 static 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.
176 static 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`
200 static 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.
217 static 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.
239 static 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 
275 void 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 
288 void 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, *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
333