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 #include "../utils/Aliasing.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>
loopEndingStmt(internal::Matcher<Stmt> Internal)23 loopEndingStmt(internal::Matcher<Stmt> Internal) {
24 return stmt(anyOf(breakStmt(Internal), returnStmt(Internal),
25 gotoStmt(Internal), cxxThrowExpr(Internal),
26 callExpr(Internal, callee(functionDecl(isNoReturn())))));
27 }
28
29 /// Return whether `Var` was changed in `LoopStmt`.
isChanged(const Stmt * LoopStmt,const VarDecl * Var,ASTContext * Context)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`.
isVarThatIsPossiblyChanged(const FunctionDecl * Func,const Stmt * LoopStmt,const Stmt * Cond,ASTContext * Context)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`.
isAtLeastOneCondVarChanged(const FunctionDecl * Func,const Stmt * LoopStmt,const Stmt * Cond,ASTContext * Context)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`.
getCondVarNames(const Stmt * 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
isKnownFalse(const Expr & Cond,const ASTContext & Ctx)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
registerMatchers(MatchFinder * Finder)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(stmt(anyOf(whileStmt(LoopCondition), doStmt(LoopCondition),
126 forStmt(LoopCondition)))
127 .bind("loop-stmt"),
128 this);
129 }
130
check(const MatchFinder::MatchResult & Result)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