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 /// 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 /// Return whether `Var` has a pointer or 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 /// Return whether `Var` has a pointer or 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 /// Return whether `Var` has a pointer or reference in `Func`.
70 static bool hasPtrOrReferenceInFunc(const FunctionDecl *Func,
71                                     const VarDecl *Var) {
72   return hasPtrOrReferenceInStmt(Func->getBody(), Var);
73 }
74 
75 /// 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 /// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`.
92 static bool isVarThatIsPossiblyChanged(const FunctionDecl *Func,
93                                        const Stmt *LoopStmt, const Stmt *Cond,
94                                        ASTContext *Context) {
95   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
96     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
97       if (!Var->isLocalVarDeclOrParm())
98         return true;
99 
100       if (Var->getType().isVolatileQualified())
101         return true;
102 
103       if (!Var->getType().getTypePtr()->isIntegerType())
104         return true;
105 
106       return hasPtrOrReferenceInFunc(Func, Var) ||
107              isChanged(LoopStmt, Var, Context);
108       // FIXME: Track references.
109     }
110   } else if (isa<MemberExpr>(Cond) || isa<CallExpr>(Cond)) {
111     // FIXME: Handle MemberExpr.
112     return true;
113   }
114 
115   return false;
116 }
117 
118 /// Return whether at least one variable of `Cond` changed in `LoopStmt`.
119 static bool isAtLeastOneCondVarChanged(const FunctionDecl *Func,
120                                        const Stmt *LoopStmt, const Stmt *Cond,
121                                        ASTContext *Context) {
122   if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
123     return true;
124 
125   for (const Stmt *Child : Cond->children()) {
126     if (!Child)
127       continue;
128 
129     if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
130       return true;
131   }
132   return false;
133 }
134 
135 /// Return the variable names in `Cond`.
136 static std::string getCondVarNames(const Stmt *Cond) {
137   if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
138     if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
139       return Var->getName();
140   }
141 
142   std::string Result;
143   for (const Stmt *Child : Cond->children()) {
144     if (!Child)
145       continue;
146 
147     std::string NewNames = getCondVarNames(Child);
148     if (!Result.empty() && !NewNames.empty())
149       Result += ", ";
150     Result += NewNames;
151   }
152   return Result;
153 }
154 
155 void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
156   const auto LoopCondition = allOf(
157       hasCondition(
158           expr(forFunction(functionDecl().bind("func"))).bind("condition")),
159       unless(hasBody(hasDescendant(
160           loopEndingStmt(forFunction(equalsBoundNode("func")))))));
161 
162   Finder->addMatcher(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
163                                 forStmt(LoopCondition)))
164                          .bind("loop-stmt"),
165                      this);
166 }
167 
168 void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
169   const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
170   const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
171   const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
172 
173   if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
174     return;
175 
176   std::string CondVarNames = getCondVarNames(Cond);
177   if (CondVarNames.empty())
178     return;
179 
180   diag(LoopStmt->getBeginLoc(),
181        "this loop is infinite; none of its condition variables (%0)"
182        " are updated in the loop body")
183       << CondVarNames;
184 }
185 
186 } // namespace bugprone
187 } // namespace tidy
188 } // namespace clang
189