llvm-project

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
#include "clang/Analysis/CallGraph.h"
15
#include "llvm/ADT/SCCIterator.h"
16
#include "llvm/ADT/SmallVector.h"
17

18
using namespace clang::ast_matchers;
19
using clang::tidy::utils::hasPtrOrReferenceInFunc;
20

21
namespace clang {
22
namespace ast_matchers {
23
/// matches a Decl if it has a  "no return" attribute of any kind
24
AST_MATCHER(Decl, declHasNoReturnAttr) {
25
  return Node.hasAttr<NoReturnAttr>() || Node.hasAttr<CXX11NoReturnAttr>() ||
26
         Node.hasAttr<C11NoReturnAttr>();
27
}
28

29
/// matches a FunctionType if the type includes the GNU no return attribute
30
AST_MATCHER(FunctionType, typeHasNoReturnAttr) {
31
  return Node.getNoReturnAttr();
32
}
33
} // namespace ast_matchers
34
namespace tidy::bugprone {
35

36
static internal::Matcher<Stmt>
37
loopEndingStmt(internal::Matcher<Stmt> Internal) {
38
  internal::Matcher<QualType> isNoReturnFunType =
39
      ignoringParens(functionType(typeHasNoReturnAttr()));
40
  internal::Matcher<Decl> isNoReturnDecl =
41
      anyOf(declHasNoReturnAttr(), functionDecl(hasType(isNoReturnFunType)),
42
            varDecl(hasType(blockPointerType(pointee(isNoReturnFunType)))));
43

44
  return stmt(anyOf(
45
      mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),
46
      callExpr(Internal,
47
               callee(mapAnyOf(functionDecl, /* block callee */ varDecl)
48
                          .with(isNoReturnDecl))),
49
      objcMessageExpr(Internal, callee(isNoReturnDecl))));
50
}
51

52
/// Return whether `Var` was changed in `LoopStmt`.
53
static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var,
54
                      ASTContext *Context) {
55
  if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))
56
    return (ForLoop->getInc() &&
57
            ExprMutationAnalyzer(*ForLoop->getInc(), *Context)
58
                .isMutated(Var)) ||
59
           (ForLoop->getBody() &&
60
            ExprMutationAnalyzer(*ForLoop->getBody(), *Context)
61
                .isMutated(Var)) ||
62
           (ForLoop->getCond() &&
63
            ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));
64

65
  return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);
66
}
67

68
/// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`.
69
static bool isVarThatIsPossiblyChanged(const Decl *Func, const Stmt *LoopStmt,
70
                                       const Stmt *Cond, ASTContext *Context) {
71
  if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
72
    if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
73
      if (!Var->isLocalVarDeclOrParm())
74
        return true;
75

76
      if (Var->getType().isVolatileQualified())
77
        return true;
78

79
      if (!Var->getType().getTypePtr()->isIntegerType())
80
        return true;
81

82
      return hasPtrOrReferenceInFunc(Func, Var) ||
83
             isChanged(LoopStmt, Var, Context);
84
      // FIXME: Track references.
85
    }
86
  } else if (isa<MemberExpr, CallExpr,
87
                 ObjCIvarRefExpr, ObjCPropertyRefExpr, ObjCMessageExpr>(Cond)) {
88
    // FIXME: Handle MemberExpr.
89
    return true;
90
  } else if (const auto *CE = dyn_cast<CastExpr>(Cond)) {
91
    QualType T = CE->getType();
92
    while (true) {
93
      if (T.isVolatileQualified())
94
        return true;
95

96
      if (!T->isAnyPointerType() && !T->isReferenceType())
97
        break;
98

99
      T = T->getPointeeType();
100
    }
101
  }
102

103
  return false;
104
}
105

106
/// Return whether at least one variable of `Cond` changed in `LoopStmt`.
107
static bool isAtLeastOneCondVarChanged(const Decl *Func, const Stmt *LoopStmt,
108
                                       const Stmt *Cond, ASTContext *Context) {
109
  if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))
110
    return true;
111

112
  for (const Stmt *Child : Cond->children()) {
113
    if (!Child)
114
      continue;
115

116
    if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))
117
      return true;
118
  }
119
  return false;
120
}
121

122
/// Return the variable names in `Cond`.
123
static std::string getCondVarNames(const Stmt *Cond) {
124
  if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
125
    if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))
126
      return std::string(Var->getName());
127
  }
128

129
  std::string Result;
130
  for (const Stmt *Child : Cond->children()) {
131
    if (!Child)
132
      continue;
133

134
    std::string NewNames = getCondVarNames(Child);
135
    if (!Result.empty() && !NewNames.empty())
136
      Result += ", ";
137
    Result += NewNames;
138
  }
139
  return Result;
140
}
141

142
static bool isKnownToHaveValue(const Expr &Cond, const ASTContext &Ctx,
143
                               bool ExpectedValue) {
144
  if (Cond.isValueDependent()) {
145
    if (const auto *BinOp = dyn_cast<BinaryOperator>(&Cond)) {
146
      // Conjunctions (disjunctions) can still be handled if at least one
147
      // conjunct (disjunct) is known to be false (true).
148
      if (!ExpectedValue && BinOp->getOpcode() == BO_LAnd)
149
        return isKnownToHaveValue(*BinOp->getLHS(), Ctx, false) ||
150
               isKnownToHaveValue(*BinOp->getRHS(), Ctx, false);
151
      if (ExpectedValue && BinOp->getOpcode() == BO_LOr)
152
        return isKnownToHaveValue(*BinOp->getLHS(), Ctx, true) ||
153
               isKnownToHaveValue(*BinOp->getRHS(), Ctx, true);
154
      if (BinOp->getOpcode() == BO_Comma)
155
        return isKnownToHaveValue(*BinOp->getRHS(), Ctx, ExpectedValue);
156
    } else if (const auto *UnOp = dyn_cast<UnaryOperator>(&Cond)) {
157
      if (UnOp->getOpcode() == UO_LNot)
158
        return isKnownToHaveValue(*UnOp->getSubExpr(), Ctx, !ExpectedValue);
159
    } else if (const auto *Paren = dyn_cast<ParenExpr>(&Cond))
160
      return isKnownToHaveValue(*Paren->getSubExpr(), Ctx, ExpectedValue);
161
    else if (const auto *ImplCast = dyn_cast<ImplicitCastExpr>(&Cond))
162
      return isKnownToHaveValue(*ImplCast->getSubExpr(), Ctx, ExpectedValue);
163
    return false;
164
  }
165
  bool Result = false;
166
  if (Cond.EvaluateAsBooleanCondition(Result, Ctx))
167
    return Result == ExpectedValue;
168
  return false;
169
}
170

171
/// populates the set `Callees` with all function (and objc method) declarations
172
/// called in `StmtNode` if all visited call sites have resolved call targets.
173
///
174
/// \return true iff all `CallExprs` visited have callees; false otherwise
175
///         indicating there is an unresolved indirect call.
176
static bool populateCallees(const Stmt *StmtNode,
177
                            llvm::SmallSet<const Decl *, 16> &Callees) {
178
  if (const auto *Call = dyn_cast<CallExpr>(StmtNode)) {
179
    const Decl *Callee = Call->getDirectCallee();
180

181
    if (!Callee)
182
      return false; // unresolved call
183
    Callees.insert(Callee->getCanonicalDecl());
184
  }
185
  if (const auto *Call = dyn_cast<ObjCMessageExpr>(StmtNode)) {
186
    const Decl *Callee = Call->getMethodDecl();
187

188
    if (!Callee)
189
      return false; // unresolved call
190
    Callees.insert(Callee->getCanonicalDecl());
191
  }
192
  for (const Stmt *Child : StmtNode->children())
193
    if (Child && !populateCallees(Child, Callees))
194
      return false;
195
  return true;
196
}
197

198
/// returns true iff `SCC` contains `Func` and its' function set overlaps with
199
/// `Callees`
200
static bool overlap(ArrayRef<CallGraphNode *> SCC,
201
                    const llvm::SmallSet<const Decl *, 16> &Callees,
202
                    const Decl *Func) {
203
  bool ContainsFunc = false, Overlap = false;
204

205
  for (const CallGraphNode *GNode : SCC) {
206
    const Decl *CanDecl = GNode->getDecl()->getCanonicalDecl();
207

208
    ContainsFunc = ContainsFunc || (CanDecl == Func);
209
    Overlap = Overlap || Callees.contains(CanDecl);
210
    if (ContainsFunc && Overlap)
211
      return true;
212
  }
213
  return false;
214
}
215

216
/// returns true iff `Cond` involves at least one static local variable.
217
static bool hasStaticLocalVariable(const Stmt *Cond) {
218
  if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond))
219
    if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()))
220
      if (VD->isStaticLocal())
221
        return true;
222
  for (const Stmt *Child : Cond->children())
223
    if (Child && hasStaticLocalVariable(Child))
224
      return true;
225
  return false;
226
}
227

228
/// Tests if the loop condition `Cond` involves static local variables and
229
/// the enclosing function `Func` is recursive.
230
///
231
///  \code
232
///    void f() {
233
///       static int i = 10;
234
///       i--;
235
///       while (i >= 0) f();
236
///    }
237
///  \endcode
238
///  The example above is NOT an infinite loop.
239
static bool hasRecursionOverStaticLoopCondVariables(const Expr *Cond,
240
                                                    const Stmt *LoopStmt,
241
                                                    const Decl *Func,
242
                                                    const ASTContext *Ctx) {
243
  if (!hasStaticLocalVariable(Cond))
244
    return false;
245

246
  llvm::SmallSet<const Decl *, 16> CalleesInLoop;
247

248
  if (!populateCallees(LoopStmt, CalleesInLoop)) {
249
    // If there are unresolved indirect calls, we assume there could
250
    // be recursion so to avoid false alarm.
251
    return true;
252
  }
253
  if (CalleesInLoop.empty())
254
    return false;
255

256
  TranslationUnitDecl *TUDecl = Ctx->getTranslationUnitDecl();
257
  CallGraph CG;
258

259
  CG.addToCallGraph(TUDecl);
260
  // For each `SCC` containing `Func`, if functions in the `SCC`
261
  // overlap with `CalleesInLoop`, there is a recursive call in `LoopStmt`.
262
  for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
263
                                       SCCE = llvm::scc_end(&CG);
264
       SCCI != SCCE; ++SCCI) {
265
    if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.
266
      continue;
267
    // `SCC`s are mutually disjoint, so there will be no redundancy in
268
    // comparing `SCC` with the callee set one by one.
269
    if (overlap(*SCCI, CalleesInLoop, Func->getCanonicalDecl()))
270
      return true;
271
  }
272
  return false;
273
}
274

275
void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {
276
  const auto LoopCondition = allOf(
277
      hasCondition(
278
          expr(forCallable(decl().bind("func"))).bind("condition")),
279
      unless(hasBody(hasDescendant(
280
          loopEndingStmt(forCallable(equalsBoundNode("func")))))));
281

282
  Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)
283
                         .with(LoopCondition)
284
                         .bind("loop-stmt"),
285
                     this);
286
}
287

288
void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {
289
  const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");
290
  const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");
291
  const auto *Func = Result.Nodes.getNodeAs<Decl>("func");
292

293
  if (isKnownToHaveValue(*Cond, *Result.Context, false))
294
    return;
295

296
  bool ShouldHaveConditionVariables = true;
297
  if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {
298
    if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {
299
      if (const Expr *Init = LoopVarDecl->getInit()) {
300
        ShouldHaveConditionVariables = false;
301
        Cond = Init;
302
      }
303
    }
304
  }
305

306
  if (ExprMutationAnalyzer::isUnevaluated(LoopStmt, *LoopStmt, *Result.Context))
307
    return;
308

309
  if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))
310
    return;
311
  if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func,
312
                                              Result.Context))
313
    return;
314

315
  std::string CondVarNames = getCondVarNames(Cond);
316
  if (ShouldHaveConditionVariables && CondVarNames.empty())
317
    return;
318

319
  if (CondVarNames.empty()) {
320
    diag(LoopStmt->getBeginLoc(),
321
         "this loop is infinite; it does not check any variables in the"
322
         " condition");
323
  } else {
324
    diag(LoopStmt->getBeginLoc(),
325
         "this loop is infinite; none of its condition variables (%0)"
326
         " are updated in the loop body")
327
      << CondVarNames;
328
  }
329
}
330

331
} // namespace tidy::bugprone
332
} // namespace clang
333