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 isKnownFalse(const Expr &Cond, const ASTContext &Ctx) {
121   if (Cond.isValueDependent())
122     return false;
123   bool Result = false;
124   if (Cond.EvaluateAsBooleanCondition(Result, Ctx))
125     return !Result;
126   return false;
127 }
128 
129 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
130   const auto LoopCondition = allOf(
131       hasCondition(
132           expr(forCallable(decl().bind("func"))).bind("condition")),
133       unless(hasBody(hasDescendant(
134           loopEndingStmt(forCallable(equalsBoundNode("func")))))));
135 
136   Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)
137                          .with(LoopCondition)
138                          .bind("loop-stmt"),
139                      this);
140 }
141 
142 void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
143   const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
144   const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
145   const auto *Func = Result.Nodes.getNodeAs<Decl>("func");
146 
147   if (isKnownFalse(*Cond, *Result.Context))
148     return;
149 
150   bool ShouldHaveConditionVariables = true;
151   if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
152     if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
153       if (const Expr *Init = LoopVarDecl->getInit()) {
154         ShouldHaveConditionVariables = false;
155         Cond = Init;
156       }
157     }
158   }
159 
160   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
161     return;
162 
163   std::string CondVarNames = getCondVarNames(Cond);
164   if (ShouldHaveConditionVariables && CondVarNames.empty())
165     return;
166 
167   if (CondVarNames.empty()) {
168     diag(LoopStmt->getBeginLoc(),
169          "this loop is infinite; it does not check any variables in the"
170          " condition");
171   } else {
172     diag(LoopStmt->getBeginLoc(),
173          "this loop is infinite; none of its condition variables (%0)"
174          " are updated in the loop body")
175       << CondVarNames;
176   }
177 }
178 
179 } // namespace bugprone
180 } // namespace tidy
181 } // namespace clang
182