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
15 using namespace clang::ast_matchers;
16 using clang::tidy::utils::hasPtrOrReferenceInFunc;
17
18 namespace clang {
19 namespace tidy {
20 namespace bugprone {
21
22 static internal::Matcher<Stmt>
loopEndingStmt(internal::Matcher<Stmt> Internal)23 loopEndingStmt(internal::Matcher<Stmt> Internal) {
24 // FIXME: Cover noreturn ObjC methods (and blocks?).
25 return stmt(anyOf(
26 mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),
27 callExpr(Internal, callee(functionDecl(isNoReturn())))));
28 }
29
30 /// Return whether `Var` was changed in `LoopStmt`.
isChanged(const Stmt * LoopStmt,const VarDecl * Var,ASTContext * Context)31 static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
32 ASTContext *Context) {
33 if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
34 return (ForLoop->getInc() &&
35 ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
36 .isMutated(Var)) ||
37 (ForLoop->getBody() &&
38 ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
39 .isMutated(Var)) ||
40 (ForLoop->getCond() &&
41 ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));
42
43 return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);
44 }
45
46 /// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`.
isVarThatIsPossiblyChanged(const Decl * Func,const Stmt * LoopStmt,const Stmt * Cond,ASTContext * Context)47 static bool isVarThatIsPossiblyChanged(const Decl *Func, const Stmt *LoopStmt,
48 const Stmt *Cond, ASTContext *Context) {
49 if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
50 if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
51 if (!Var->isLocalVarDeclOrParm())
52 return true;
53
54 if (Var->getType().isVolatileQualified())
55 return true;
56
57 if (!Var->getType().getTypePtr()->isIntegerType())
58 return true;
59
60 return hasPtrOrReferenceInFunc(Func, Var) ||
61 isChanged(LoopStmt, Var, Context);
62 // FIXME: Track references.
63 }
64 } else if (isa<MemberExpr, CallExpr,
65 ObjCIvarRefExpr, ObjCPropertyRefExpr, ObjCMessageExpr>(Cond)) {
66 // FIXME: Handle MemberExpr.
67 return true;
68 } else if (const auto *CE = dyn_cast<CastExpr>(Cond)) {
69 QualType T = CE->getType();
70 while (true) {
71 if (T.isVolatileQualified())
72 return true;
73
74 if (!T->isAnyPointerType() && !T->isReferenceType())
75 break;
76
77 T = T->getPointeeType();
78 }
79 }
80
81 return false;
82 }
83
84 /// Return whether at least one variable of `Cond` changed in `LoopStmt`.
isAtLeastOneCondVarChanged(const Decl * Func,const Stmt * LoopStmt,const Stmt * Cond,ASTContext * Context)85 static bool isAtLeastOneCondVarChanged(const Decl *Func, const Stmt *LoopStmt,
86 const Stmt *Cond, ASTContext *Context) {
87 if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
88 return true;
89
90 for (const Stmt *Child : Cond->children()) {
91 if (!Child)
92 continue;
93
94 if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
95 return true;
96 }
97 return false;
98 }
99
100 /// Return the variable names in `Cond`.
getCondVarNames(const Stmt * Cond)101 static std::string getCondVarNames(const Stmt *Cond) {
102 if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
103 if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
104 return std::string(Var->getName());
105 }
106
107 std::string Result;
108 for (const Stmt *Child : Cond->children()) {
109 if (!Child)
110 continue;
111
112 std::string NewNames = getCondVarNames(Child);
113 if (!Result.empty() && !NewNames.empty())
114 Result += ", ";
115 Result += NewNames;
116 }
117 return Result;
118 }
119
isKnownToHaveValue(const Expr & Cond,const ASTContext & Ctx,bool ExpectedValue)120 static bool isKnownToHaveValue(const Expr &Cond, const ASTContext &Ctx,
121 bool ExpectedValue) {
122 if (Cond.isValueDependent()) {
123 if (const auto *BinOp = dyn_cast<BinaryOperator>(&Cond)) {
124 // Conjunctions (disjunctions) can still be handled if at least one
125 // conjunct (disjunct) is known to be false (true).
126 if (!ExpectedValue && BinOp->getOpcode() == BO_LAnd)
127 return isKnownToHaveValue(*BinOp->getLHS(), Ctx, false) ||
128 isKnownToHaveValue(*BinOp->getRHS(), Ctx, false);
129 if (ExpectedValue && BinOp->getOpcode() == BO_LOr)
130 return isKnownToHaveValue(*BinOp->getLHS(), Ctx, true) ||
131 isKnownToHaveValue(*BinOp->getRHS(), Ctx, true);
132 if (BinOp->getOpcode() == BO_Comma)
133 return isKnownToHaveValue(*BinOp->getRHS(), Ctx, ExpectedValue);
134 } else if (const auto *UnOp = dyn_cast<UnaryOperator>(&Cond)) {
135 if (UnOp->getOpcode() == UO_LNot)
136 return isKnownToHaveValue(*UnOp->getSubExpr(), Ctx, !ExpectedValue);
137 } else if (const auto *Paren = dyn_cast<ParenExpr>(&Cond))
138 return isKnownToHaveValue(*Paren->getSubExpr(), Ctx, ExpectedValue);
139 else if (const auto *ImplCast = dyn_cast<ImplicitCastExpr>(&Cond))
140 return isKnownToHaveValue(*ImplCast->getSubExpr(), Ctx, ExpectedValue);
141 return false;
142 }
143 bool Result = false;
144 if (Cond.EvaluateAsBooleanCondition(Result, Ctx))
145 return Result == ExpectedValue;
146 return false;
147 }
148
registerMatchers(MatchFinder * Finder)149 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
150 const auto LoopCondition = allOf(
151 hasCondition(
152 expr(forCallable(decl().bind("func"))).bind("condition")),
153 unless(hasBody(hasDescendant(
154 loopEndingStmt(forCallable(equalsBoundNode("func")))))));
155
156 Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)
157 .with(LoopCondition)
158 .bind("loop-stmt"),
159 this);
160 }
161
check(const MatchFinder::MatchResult & Result)162 void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
163 const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
164 const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
165 const auto *Func = Result.Nodes.getNodeAs<Decl>("func");
166
167 if (isKnownToHaveValue(*Cond, *Result.Context, false))
168 return;
169
170 bool ShouldHaveConditionVariables = true;
171 if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
172 if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
173 if (const Expr *Init = LoopVarDecl->getInit()) {
174 ShouldHaveConditionVariables = false;
175 Cond = Init;
176 }
177 }
178 }
179
180 if (ExprMutationAnalyzer::isUnevaluated(LoopStmt, *LoopStmt, *Result.Context))
181 return;
182
183 if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
184 return;
185
186 std::string CondVarNames = getCondVarNames(Cond);
187 if (ShouldHaveConditionVariables && CondVarNames.empty())
188 return;
189
190 if (CondVarNames.empty()) {
191 diag(LoopStmt->getBeginLoc(),
192 "this loop is infinite; it does not check any variables in the"
193 " condition");
194 } else {
195 diag(LoopStmt->getBeginLoc(),
196 "this loop is infinite; none of its condition variables (%0)"
197 " are updated in the loop body")
198 << CondVarNames;
199 }
200 }
201
202 } // namespace bugprone
203 } // namespace tidy
204 } // namespace clang
205