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   return stmt(anyOf(
25       mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),
26       callExpr(Internal, callee(functionDecl(isNoReturn())))));
27 }
28 
29 /// Return whether `Var` was changed in `LoopStmt`.
30 static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
31                       ASTContext *Context) {
32   if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
33     return (ForLoop->getInc() &&
34             ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
35                 .isMutated(Var)) ||
36            (ForLoop->getBody() &&
37             ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
38                 .isMutated(Var)) ||
39            (ForLoop->getCond() &&
40             ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));
41 
42   return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);
43 }
44 
45 /// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`.
46 static bool isVarThatIsPossiblyChanged(const FunctionDecl *Func,
47                                        const Stmt *LoopStmt, const Stmt *Cond,
48                                        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>(Cond) || isa<CallExpr>(Cond)) {
65     // FIXME: Handle MemberExpr.
66     return true;
67   }
68 
69   return false;
70 }
71 
72 /// Return whether at least one variable of `Cond` changed in `LoopStmt`.
73 static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func,
74                                        const Stmt *LoopStmt, const Stmt *Cond,
75                                        ASTContext *Context) {
76   if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
77     return true;
78 
79   for (const Stmt *Child : Cond->children()) {
80     if (!Child)
81       continue;
82 
83     if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
84       return true;
85   }
86   return false;
87 }
88 
89 /// Return the variable names in `Cond`.
90 static std::string getCondVarNames(const Stmt *Cond) {
91   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
92     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
93       return std::string(Var->getName());
94   }
95 
96   std::string Result;
97   for (const Stmt *Child : Cond->children()) {
98     if (!Child)
99       continue;
100 
101     std::string NewNames = getCondVarNames(Child);
102     if (!Result.empty() && !NewNames.empty())
103       Result += ", ";
104     Result += NewNames;
105   }
106   return Result;
107 }
108 
109 static bool isKnownFalse(const Expr &Cond, const ASTContext &Ctx) {
110   if (Cond.isValueDependent())
111     return false;
112   bool Result = false;
113   if (Cond.EvaluateAsBooleanCondition(Result, Ctx))
114     return !Result;
115   return false;
116 }
117 
118 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
119   const auto LoopCondition = allOf(
120       hasCondition(
121           expr(forFunction(functionDecl().bind("func"))).bind("condition")),
122       unless(hasBody(hasDescendant(
123           loopEndingStmt(forFunction(equalsBoundNode("func")))))));
124 
125   Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)
126                          .with(LoopCondition)
127                          .bind("loop-stmt"),
128                      this);
129 }
130 
131 void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
132   const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
133   const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
134   const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
135 
136   if (isKnownFalse(*Cond, *Result.Context))
137     return;
138 
139   bool ShouldHaveConditionVariables = true;
140   if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
141     if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
142       if (const Expr *Init = LoopVarDecl->getInit()) {
143         ShouldHaveConditionVariables = false;
144         Cond = Init;
145       }
146     }
147   }
148 
149   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
150     return;
151 
152   std::string CondVarNames = getCondVarNames(Cond);
153   if (ShouldHaveConditionVariables && CondVarNames.empty())
154     return;
155 
156   if (CondVarNames.empty()) {
157     diag(LoopStmt->getBeginLoc(),
158          "this loop is infinite; it does not check any variables in the"
159          " condition");
160   } else {
161     diag(LoopStmt->getBeginLoc(),
162          "this loop is infinite; none of its condition variables (%0)"
163          " are updated in the loop body")
164       << CondVarNames;
165   }
166 }
167 
168 } // namespace bugprone
169 } // namespace tidy
170 } // namespace clang
171