352 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//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 17using namespace clang::ast_matchers;18using clang::ast_matchers::internal::Matcher;19using clang::tidy::utils::hasPtrOrReferenceInFunc;20 21namespace clang::tidy::bugprone {22 23namespace {24/// matches a Decl if it has a "no return" attribute of any kind25AST_MATCHER(Decl, declHasNoReturnAttr) {26 return Node.hasAttr<NoReturnAttr>() || Node.hasAttr<CXX11NoReturnAttr>() ||27 Node.hasAttr<C11NoReturnAttr>();28}29 30/// matches a FunctionType if the type includes the GNU no return attribute31AST_MATCHER(FunctionType, typeHasNoReturnAttr) {32 return Node.getNoReturnAttr();33}34} // namespace35 36static Matcher<Stmt> loopEndingStmt(Matcher<Stmt> Internal) {37 const Matcher<QualType> IsNoReturnFunType =38 ignoringParens(functionType(typeHasNoReturnAttr()));39 Matcher<Decl> IsNoReturnDecl =40 anyOf(declHasNoReturnAttr(), functionDecl(hasType(IsNoReturnFunType)),41 varDecl(hasType(blockPointerType(pointee(IsNoReturnFunType)))));42 43 return stmt(anyOf(44 mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal),45 callExpr(Internal,46 callee(mapAnyOf(functionDecl, /* block callee */ varDecl)47 .with(IsNoReturnDecl))),48 objcMessageExpr(Internal, callee(IsNoReturnDecl))));49}50 51/// Return whether `Var` was changed in `LoopStmt`.52static bool isChanged(const Stmt *LoopStmt, const ValueDecl *Var,53 ASTContext *Context) {54 if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt))55 return (ForLoop->getInc() &&56 ExprMutationAnalyzer(*ForLoop->getInc(), *Context)57 .isMutated(Var)) ||58 (ForLoop->getBody() &&59 ExprMutationAnalyzer(*ForLoop->getBody(), *Context)60 .isMutated(Var)) ||61 (ForLoop->getCond() &&62 ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var));63 64 return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var);65}66 67static bool isVarPossiblyChanged(const Decl *Func, const Stmt *LoopStmt,68 const ValueDecl *VD, ASTContext *Context) {69 const VarDecl *Var = nullptr;70 if (const auto *VarD = dyn_cast<VarDecl>(VD)) {71 Var = VarD;72 } else if (const auto *BD = dyn_cast<BindingDecl>(VD)) {73 if (const auto *DD = dyn_cast<DecompositionDecl>(BD->getDecomposedDecl()))74 Var = DD;75 }76 77 if (!Var)78 return false;79 80 if (!Var->isLocalVarDeclOrParm() || Var->getType().isVolatileQualified())81 return true;82 83 if (!VD->getType().getTypePtr()->isIntegerType())84 return true;85 86 return hasPtrOrReferenceInFunc(Func, VD) || isChanged(LoopStmt, VD, Context);87 // FIXME: Track references.88}89 90/// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`.91static bool isVarThatIsPossiblyChanged(const Decl *Func, const Stmt *LoopStmt,92 const Stmt *Cond, ASTContext *Context) {93 if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {94 if (const auto *VD = dyn_cast<ValueDecl>(DRE->getDecl()))95 return isVarPossiblyChanged(Func, LoopStmt, VD, Context);96 } else if (isa<MemberExpr, CallExpr, ObjCIvarRefExpr, ObjCPropertyRefExpr,97 ObjCMessageExpr>(Cond)) {98 // FIXME: Handle MemberExpr.99 return true;100 } else if (const auto *CE = dyn_cast<CastExpr>(Cond)) {101 QualType T = CE->getType();102 while (true) {103 if (T.isVolatileQualified())104 return true;105 106 if (!T->isAnyPointerType() && !T->isReferenceType())107 break;108 109 T = T->getPointeeType();110 }111 }112 113 return false;114}115 116/// Return whether at least one variable of `Cond` changed in `LoopStmt`.117static bool isAtLeastOneCondVarChanged(const Decl *Func, const Stmt *LoopStmt,118 const Stmt *Cond, ASTContext *Context) {119 if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context))120 return true;121 122 for (const Stmt *Child : Cond->children()) {123 if (!Child)124 continue;125 126 if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context))127 return true;128 }129 return false;130}131 132/// Return the variable names in `Cond`.133static std::string getCondVarNames(const Stmt *Cond) {134 if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {135 if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl()))136 return std::string(Var->getName());137 138 if (const auto *BD = dyn_cast<BindingDecl>(DRE->getDecl())) {139 return std::string(BD->getName());140 }141 }142 143 std::string Result;144 for (const Stmt *Child : Cond->children()) {145 if (!Child)146 continue;147 148 const std::string NewNames = getCondVarNames(Child);149 if (!Result.empty() && !NewNames.empty())150 Result += ", ";151 Result += NewNames;152 }153 return Result;154}155 156static bool isKnownToHaveValue(const Expr &Cond, const ASTContext &Ctx,157 bool ExpectedValue) {158 if (Cond.isValueDependent()) {159 if (const auto *BinOp = dyn_cast<BinaryOperator>(&Cond)) {160 // Conjunctions (disjunctions) can still be handled if at least one161 // conjunct (disjunct) is known to be false (true).162 if (!ExpectedValue && BinOp->getOpcode() == BO_LAnd)163 return isKnownToHaveValue(*BinOp->getLHS(), Ctx, false) ||164 isKnownToHaveValue(*BinOp->getRHS(), Ctx, false);165 if (ExpectedValue && BinOp->getOpcode() == BO_LOr)166 return isKnownToHaveValue(*BinOp->getLHS(), Ctx, true) ||167 isKnownToHaveValue(*BinOp->getRHS(), Ctx, true);168 if (BinOp->getOpcode() == BO_Comma)169 return isKnownToHaveValue(*BinOp->getRHS(), Ctx, ExpectedValue);170 } else if (const auto *UnOp = dyn_cast<UnaryOperator>(&Cond)) {171 if (UnOp->getOpcode() == UO_LNot)172 return isKnownToHaveValue(*UnOp->getSubExpr(), Ctx, !ExpectedValue);173 } else if (const auto *Paren = dyn_cast<ParenExpr>(&Cond))174 return isKnownToHaveValue(*Paren->getSubExpr(), Ctx, ExpectedValue);175 else if (const auto *ImplCast = dyn_cast<ImplicitCastExpr>(&Cond))176 return isKnownToHaveValue(*ImplCast->getSubExpr(), Ctx, ExpectedValue);177 return false;178 }179 bool Result = false;180 if (Cond.EvaluateAsBooleanCondition(Result, Ctx))181 return Result == ExpectedValue;182 return false;183}184 185/// populates the set `Callees` with all function (and objc method) declarations186/// called in `StmtNode` if all visited call sites have resolved call targets.187///188/// \return true iff all `CallExprs` visited have callees; false otherwise189/// indicating there is an unresolved indirect call.190static bool populateCallees(const Stmt *StmtNode,191 llvm::SmallPtrSet<const Decl *, 16> &Callees) {192 if (const auto *Call = dyn_cast<CallExpr>(StmtNode)) {193 const Decl *Callee = Call->getDirectCallee();194 195 if (!Callee)196 return false; // unresolved call197 Callees.insert(Callee->getCanonicalDecl());198 }199 if (const auto *Call = dyn_cast<ObjCMessageExpr>(StmtNode)) {200 const Decl *Callee = Call->getMethodDecl();201 202 if (!Callee)203 return false; // unresolved call204 Callees.insert(Callee->getCanonicalDecl());205 }206 for (const Stmt *Child : StmtNode->children())207 if (Child && !populateCallees(Child, Callees))208 return false;209 return true;210}211 212/// returns true iff `SCC` contains `Func` and its' function set overlaps with213/// `Callees`214static bool overlap(ArrayRef<CallGraphNode *> SCC,215 const llvm::SmallPtrSet<const Decl *, 16> &Callees,216 const Decl *Func) {217 bool ContainsFunc = false, Overlap = false;218 219 for (const CallGraphNode *GNode : SCC) {220 const Decl *CanDecl = GNode->getDecl()->getCanonicalDecl();221 222 ContainsFunc = ContainsFunc || (CanDecl == Func);223 Overlap = Overlap || Callees.contains(CanDecl);224 if (ContainsFunc && Overlap)225 return true;226 }227 return false;228}229 230/// returns true iff `Cond` involves at least one static local variable.231static bool hasStaticLocalVariable(const Stmt *Cond) {232 if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {233 if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()))234 if (VD->isStaticLocal())235 return true;236 237 if (const auto *BD = dyn_cast<BindingDecl>(DRE->getDecl()))238 if (const auto *DD = dyn_cast<DecompositionDecl>(BD->getDecomposedDecl()))239 if (DD->isStaticLocal())240 return true;241 }242 243 for (const Stmt *Child : Cond->children())244 if (Child && hasStaticLocalVariable(Child))245 return true;246 return false;247}248 249/// Tests if the loop condition `Cond` involves static local variables and250/// the enclosing function `Func` is recursive.251///252/// \code253/// void f() {254/// static int i = 10;255/// i--;256/// while (i >= 0) f();257/// }258/// \endcode259/// The example above is NOT an infinite loop.260static bool hasRecursionOverStaticLoopCondVariables(const Expr *Cond,261 const Stmt *LoopStmt,262 const Decl *Func,263 const ASTContext *Ctx) {264 if (!hasStaticLocalVariable(Cond))265 return false;266 267 llvm::SmallPtrSet<const Decl *, 16> CalleesInLoop;268 269 if (!populateCallees(LoopStmt, CalleesInLoop)) {270 // If there are unresolved indirect calls, we assume there could271 // be recursion so to avoid false alarm.272 return true;273 }274 if (CalleesInLoop.empty())275 return false;276 277 TranslationUnitDecl *TUDecl = Ctx->getTranslationUnitDecl();278 CallGraph CG;279 280 CG.addToCallGraph(TUDecl);281 // For each `SCC` containing `Func`, if functions in the `SCC`282 // overlap with `CalleesInLoop`, there is a recursive call in `LoopStmt`.283 for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),284 SCCE = llvm::scc_end(&CG);285 SCCI != SCCE; ++SCCI) {286 if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.287 continue;288 // `SCC`s are mutually disjoint, so there will be no redundancy in289 // comparing `SCC` with the callee set one by one.290 if (overlap(*SCCI, CalleesInLoop, Func->getCanonicalDecl()))291 return true;292 }293 return false;294}295 296void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) {297 const auto LoopCondition = allOf(298 hasCondition(expr(forCallable(decl().bind("func"))).bind("condition")),299 unless(hasBody(hasDescendant(300 loopEndingStmt(forCallable(equalsBoundNode("func")))))));301 302 Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt)303 .with(LoopCondition)304 .bind("loop-stmt"),305 this);306}307 308void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) {309 const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition");310 const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt");311 const auto *Func = Result.Nodes.getNodeAs<Decl>("func");312 313 if (isKnownToHaveValue(*Cond, *Result.Context, false))314 return;315 316 bool ShouldHaveConditionVariables = true;317 if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) {318 if (const VarDecl *LoopVarDecl = While->getConditionVariable()) {319 if (const Expr *Init = LoopVarDecl->getInit()) {320 ShouldHaveConditionVariables = false;321 Cond = Init;322 }323 }324 }325 326 if (ExprMutationAnalyzer::isUnevaluated(LoopStmt, *Result.Context))327 return;328 329 if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context))330 return;331 if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func,332 Result.Context))333 return;334 335 const std::string CondVarNames = getCondVarNames(Cond);336 if (ShouldHaveConditionVariables && CondVarNames.empty())337 return;338 339 if (CondVarNames.empty()) {340 diag(LoopStmt->getBeginLoc(),341 "this loop is infinite; it does not check any variables in the"342 " condition");343 } else {344 diag(LoopStmt->getBeginLoc(),345 "this loop is infinite; none of its condition variables (%0)"346 " are updated in the loop body")347 << CondVarNames;348 }349}350 351} // namespace clang::tidy::bugprone352