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 "clang/AST/ASTContext.h"
11 #include "clang/ASTMatchers/ASTMatchFinder.h"
12 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
13 
14 using namespace clang::ast_matchers;
15 
16 namespace clang {
17 namespace tidy {
18 namespace bugprone {
19 
20 static internal::Matcher<Stmt>
21 loopEndingStmt(internal::Matcher<Stmt> Internal) {
22   return stmt(anyOf(breakStmt(Internal), returnStmt(Internal),
23                     gotoStmt(Internal), cxxThrowExpr(Internal),
24                     callExpr(Internal, callee(functionDecl(isNoReturn())))));
25 }
26 
27 /// \brief Return whether `S` is a reference to the declaration of `Var`.
28 static bool isAccessForVar(const Stmt *S, const VarDecl *Var) {
29   if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
30     return DRE->getDecl() == Var;
31 
32   return false;
33 }
34 
35 /// \brief Return whether `Var` has a pointer of reference in `S`.
36 static bool isPtrOrReferenceForVar(const Stmt *S, const VarDecl *Var) {
37   if (const auto *DS = dyn_cast<DeclStmt>(S)) {
38     for (const Decl *D : DS->getDeclGroup()) {
39       if (const auto *LeftVar = dyn_cast<VarDecl>(D)) {
40         if (LeftVar->hasInit() && LeftVar->getType()->isReferenceType()) {
41           return isAccessForVar(LeftVar->getInit(), Var);
42         }
43       }
44     }
45   } else if (const auto *UnOp = dyn_cast<UnaryOperator>(S)) {
46     if (UnOp->getOpcode() == UO_AddrOf)
47       return isAccessForVar(UnOp->getSubExpr(), Var);
48   }
49 
50   return false;
51 }
52 
53 /// \brief Return whether `Var` has a pointer of reference in `S`.
54 static bool hasPtrOrReferenceInStmt(const Stmt *S, const VarDecl *Var) {
55   if (isPtrOrReferenceForVar(S, Var))
56     return true;
57 
58   for (const Stmt *Child : S->children()) {
59     if (!Child)
60       continue;
61 
62     if (hasPtrOrReferenceInStmt(Child, Var))
63       return true;
64   }
65 
66   return false;
67 }
68 
69 /// \brief Return whether `Var` has a pointer of reference in `Func`.
70 static bool hasPtrOrReferenceInFunc(const FunctionDecl *Func,
71                                     const VarDecl *Var) {
72   return hasPtrOrReferenceInStmt(Func->getBody(), Var);
73 }
74 
75 /// \brief Return whether `Var` was changed in `LoopStmt`.
76 static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
77                       ASTContext *Context) {
78   if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
79     return (ForLoop->getInc() &&
80             ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
81                 .isMutated(Var)) ||
82            (ForLoop->getBody() &&
83             ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
84                 .isMutated(Var)) ||
85            (ForLoop->getCond() &&
86             ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));
87 
88   return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);
89 }
90 
91 /// \brief Return whether `Cond` is a variable that is possibly changed in
92 /// `LoopStmt`.
93 static bool isVarThatIsPossiblyChanged(const FunctionDecl *Func,
94                                        const Stmt *LoopStmt, const Stmt *Cond,
95                                        ASTContext *Context) {
96   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
97     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
98       if (!Var->isLocalVarDeclOrParm())
99         return true;
100 
101       if (Var->getType().isVolatileQualified())
102         return true;
103 
104       if (!Var->getType().getTypePtr()->isIntegerType())
105         return true;
106 
107       return hasPtrOrReferenceInFunc(Func, Var) ||
108              isChanged(LoopStmt, Var, Context);
109       // FIXME: Track references.
110     }
111   } else if (isa<MemberExpr>(Cond) || isa<CallExpr>(Cond)) {
112     // FIXME: Handle MemberExpr.
113     return true;
114   }
115 
116   return false;
117 }
118 
119 /// \brief Return whether at least one variable of `Cond` changed in `LoopStmt`.
120 static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func,
121                                        const Stmt *LoopStmt, const Stmt *Cond,
122                                        ASTContext *Context) {
123   if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
124     return true;
125 
126   for (const Stmt *Child : Cond->children()) {
127     if (!Child)
128       continue;
129 
130     if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
131       return true;
132   }
133   return false;
134 }
135 
136 /// \brief Return the variable names in `Cond`.
137 static std::string getCondVarNames(const Stmt *Cond) {
138   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
139     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
140       return Var->getName();
141   }
142 
143   std::string Result;
144   for (const Stmt *Child : Cond->children()) {
145     if (!Child)
146       continue;
147 
148     std::string NewNames = getCondVarNames(Child);
149     if (!Result.empty() && !NewNames.empty())
150       Result += ", ";
151     Result += NewNames;
152   }
153   return Result;
154 }
155 
156 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
157   const auto LoopCondition = allOf(
158       hasCondition(
159           expr(forFunction(functionDecl().bind("func"))).bind("condition")),
160       unless(hasBody(hasDescendant(
161           loopEndingStmt(forFunction(equalsBoundNode("func")))))));
162 
163   Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
164                                 forStmt(LoopCondition)))
165                          .bind("loop-stmt"),
166                      this);
167 }
168 
169 void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
170   const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
171   const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
172   const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
173 
174   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
175     return;
176 
177   std::string CondVarNames = getCondVarNames(Cond);
178   if (CondVarNames.empty())
179     return;
180 
181   diag(LoopStmt->getBeginLoc(),
182        "this loop is infinite; none of its condition variables (%0)"
183        " are updated in the loop body")
184       << CondVarNames;
185 }
186 
187 } // namespace bugprone
188 } // namespace tidy
189 } // namespace clang
190