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>
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`.
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`.
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`.
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`.
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 
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 
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 
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 (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
181     return;
182 
183   std::string CondVarNames = getCondVarNames(Cond);
184   if (ShouldHaveConditionVariables && CondVarNames.empty())
185     return;
186 
187   if (CondVarNames.empty()) {
188     diag(LoopStmt->getBeginLoc(),
189          "this loop is infinite; it does not check any variables in the"
190          " condition");
191   } else {
192     diag(LoopStmt->getBeginLoc(),
193          "this loop is infinite; none of its condition variables (%0)"
194          " are updated in the loop body")
195       << CondVarNames;
196   }
197 }
198 
199 } // namespace bugprone
200 } // namespace tidy
201 } // namespace clang
202