clang-tools  14.0.0git
InfiniteLoopCheck.cpp
Go to the documentation of this file.
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;
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
clang::tidy::bugprone::isChanged
static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var, ASTContext *Context)
Return whether Var was changed in LoopStmt.
Definition: InfiniteLoopCheck.cpp:31
Ctx
Context Ctx
Definition: TUScheduler.cpp:460
clang::tidy::bugprone::isKnownFalse
static bool isKnownFalse(const Expr &Cond, const ASTContext &Ctx)
Definition: InfiniteLoopCheck.cpp:120
clang::ast_matchers
Definition: AbseilMatcher.h:14
Decl
const FunctionDecl * Decl
Definition: AvoidBindCheck.cpp:100
clang::tidy::bugprone::isVarThatIsPossiblyChanged
static bool isVarThatIsPossiblyChanged(const Decl *Func, const Stmt *LoopStmt, const Stmt *Cond, ASTContext *Context)
Return whether Cond is a variable that is possibly changed in LoopStmt.
Definition: InfiniteLoopCheck.cpp:47
clang::tidy::utils::hasPtrOrReferenceInFunc
bool hasPtrOrReferenceInFunc(const Decl *Func, const VarDecl *Var)
Returns whether Var has a pointer or reference in Func.
Definition: Aliasing.cpp:94
clang::clangd::check
bool check(llvm::StringRef File, llvm::function_ref< bool(const Position &)> ShouldCheckLine, const ThreadsafeFS &TFS, const ClangdLSPServer::Options &Opts, bool EnableCodeCompletion)
Definition: Check.cpp:259
clang::tidy::bugprone::isAtLeastOneCondVarChanged
static bool isAtLeastOneCondVarChanged(const Decl *Func, const Stmt *LoopStmt, const Stmt *Cond, ASTContext *Context)
Return whether at least one variable of Cond changed in LoopStmt.
Definition: InfiniteLoopCheck.cpp:85
CE
CaptureExpr CE
Definition: AvoidBindCheck.cpp:67
clang::tidy::bugprone::loopEndingStmt
static internal::Matcher< Stmt > loopEndingStmt(internal::Matcher< Stmt > Internal)
Definition: InfiniteLoopCheck.cpp:23
InfiniteLoopCheck.h
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::tidy::bugprone::getCondVarNames
static std::string getCondVarNames(const Stmt *Cond)
Return the variable names in Cond.
Definition: InfiniteLoopCheck.cpp:101