| //===--- InfiniteLoopCheck.cpp - clang-tidy -------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "InfiniteLoopCheck.h" |
| #include "../utils/Aliasing.h" |
| #include "clang/AST/ASTContext.h" |
| #include "clang/ASTMatchers/ASTMatchFinder.h" |
| #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h" |
| #include "clang/Analysis/CallGraph.h" |
| #include "llvm/ADT/SCCIterator.h" |
| #include "llvm/ADT/SmallVector.h" |
| |
| using namespace clang::ast_matchers; |
| using clang::tidy::utils::hasPtrOrReferenceInFunc; |
| |
| namespace clang { |
| namespace ast_matchers { |
| /// matches a Decl if it has a "no return" attribute of any kind |
| AST_MATCHER(Decl, declHasNoReturnAttr) { |
| return Node.hasAttr<NoReturnAttr>() || Node.hasAttr<CXX11NoReturnAttr>() || |
| Node.hasAttr<C11NoReturnAttr>(); |
| } |
| |
| /// matches a FunctionType if the type includes the GNU no return attribute |
| AST_MATCHER(FunctionType, typeHasNoReturnAttr) { |
| return Node.getNoReturnAttr(); |
| } |
| } // namespace ast_matchers |
| namespace tidy::bugprone { |
| |
| static internal::Matcher<Stmt> |
| loopEndingStmt(internal::Matcher<Stmt> Internal) { |
| internal::Matcher<QualType> isNoReturnFunType = |
| ignoringParens(functionType(typeHasNoReturnAttr())); |
| internal::Matcher<Decl> isNoReturnDecl = |
| anyOf(declHasNoReturnAttr(), functionDecl(hasType(isNoReturnFunType)), |
| varDecl(hasType(blockPointerType(pointee(isNoReturnFunType))))); |
| |
| return stmt(anyOf( |
| mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal), |
| callExpr(Internal, |
| callee(mapAnyOf(functionDecl, /* block callee */ varDecl) |
| .with(isNoReturnDecl))), |
| objcMessageExpr(Internal, callee(isNoReturnDecl)))); |
| } |
| |
| /// Return whether `Var` was changed in `LoopStmt`. |
| static bool isChanged(const Stmt *LoopStmt, const VarDecl *Var, |
| ASTContext *Context) { |
| if (const auto *ForLoop = dyn_cast<ForStmt>(LoopStmt)) |
| return (ForLoop->getInc() && |
| ExprMutationAnalyzer(*ForLoop->getInc(), *Context) |
| .isMutated(Var)) || |
| (ForLoop->getBody() && |
| ExprMutationAnalyzer(*ForLoop->getBody(), *Context) |
| .isMutated(Var)) || |
| (ForLoop->getCond() && |
| ExprMutationAnalyzer(*ForLoop->getCond(), *Context).isMutated(Var)); |
| |
| return ExprMutationAnalyzer(*LoopStmt, *Context).isMutated(Var); |
| } |
| |
| /// Return whether `Cond` is a variable that is possibly changed in `LoopStmt`. |
| static bool isVarThatIsPossiblyChanged(const Decl *Func, const Stmt *LoopStmt, |
| const Stmt *Cond, ASTContext *Context) { |
| if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) { |
| if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) { |
| if (!Var->isLocalVarDeclOrParm()) |
| return true; |
| |
| if (Var->getType().isVolatileQualified()) |
| return true; |
| |
| if (!Var->getType().getTypePtr()->isIntegerType()) |
| return true; |
| |
| return hasPtrOrReferenceInFunc(Func, Var) || |
| isChanged(LoopStmt, Var, Context); |
| // FIXME: Track references. |
| } |
| } else if (isa<MemberExpr, CallExpr, |
| ObjCIvarRefExpr, ObjCPropertyRefExpr, ObjCMessageExpr>(Cond)) { |
| // FIXME: Handle MemberExpr. |
| return true; |
| } else if (const auto *CE = dyn_cast<CastExpr>(Cond)) { |
| QualType T = CE->getType(); |
| while (true) { |
| if (T.isVolatileQualified()) |
| return true; |
| |
| if (!T->isAnyPointerType() && !T->isReferenceType()) |
| break; |
| |
| T = T->getPointeeType(); |
| } |
| } |
| |
| return false; |
| } |
| |
| /// Return whether at least one variable of `Cond` changed in `LoopStmt`. |
| static bool isAtLeastOneCondVarChanged(const Decl *Func, const Stmt *LoopStmt, |
| const Stmt *Cond, ASTContext *Context) { |
| if (isVarThatIsPossiblyChanged(Func, LoopStmt, Cond, Context)) |
| return true; |
| |
| for (const Stmt *Child : Cond->children()) { |
| if (!Child) |
| continue; |
| |
| if (isAtLeastOneCondVarChanged(Func, LoopStmt, Child, Context)) |
| return true; |
| } |
| return false; |
| } |
| |
| /// Return the variable names in `Cond`. |
| static std::string getCondVarNames(const Stmt *Cond) { |
| if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) { |
| if (const auto *Var = dyn_cast<VarDecl>(DRE->getDecl())) |
| return std::string(Var->getName()); |
| } |
| |
| std::string Result; |
| for (const Stmt *Child : Cond->children()) { |
| if (!Child) |
| continue; |
| |
| std::string NewNames = getCondVarNames(Child); |
| if (!Result.empty() && !NewNames.empty()) |
| Result += ", "; |
| Result += NewNames; |
| } |
| return Result; |
| } |
| |
| static bool isKnownToHaveValue(const Expr &Cond, const ASTContext &Ctx, |
| bool ExpectedValue) { |
| if (Cond.isValueDependent()) { |
| if (const auto *BinOp = dyn_cast<BinaryOperator>(&Cond)) { |
| // Conjunctions (disjunctions) can still be handled if at least one |
| // conjunct (disjunct) is known to be false (true). |
| if (!ExpectedValue && BinOp->getOpcode() == BO_LAnd) |
| return isKnownToHaveValue(*BinOp->getLHS(), Ctx, false) || |
| isKnownToHaveValue(*BinOp->getRHS(), Ctx, false); |
| if (ExpectedValue && BinOp->getOpcode() == BO_LOr) |
| return isKnownToHaveValue(*BinOp->getLHS(), Ctx, true) || |
| isKnownToHaveValue(*BinOp->getRHS(), Ctx, true); |
| if (BinOp->getOpcode() == BO_Comma) |
| return isKnownToHaveValue(*BinOp->getRHS(), Ctx, ExpectedValue); |
| } else if (const auto *UnOp = dyn_cast<UnaryOperator>(&Cond)) { |
| if (UnOp->getOpcode() == UO_LNot) |
| return isKnownToHaveValue(*UnOp->getSubExpr(), Ctx, !ExpectedValue); |
| } else if (const auto *Paren = dyn_cast<ParenExpr>(&Cond)) |
| return isKnownToHaveValue(*Paren->getSubExpr(), Ctx, ExpectedValue); |
| else if (const auto *ImplCast = dyn_cast<ImplicitCastExpr>(&Cond)) |
| return isKnownToHaveValue(*ImplCast->getSubExpr(), Ctx, ExpectedValue); |
| return false; |
| } |
| bool Result = false; |
| if (Cond.EvaluateAsBooleanCondition(Result, Ctx)) |
| return Result == ExpectedValue; |
| return false; |
| } |
| |
| /// populates the set `Callees` with all function (and objc method) declarations |
| /// called in `StmtNode` if all visited call sites have resolved call targets. |
| /// |
| /// \return true iff all `CallExprs` visited have callees; false otherwise |
| /// indicating there is an unresolved indirect call. |
| static bool populateCallees(const Stmt *StmtNode, |
| llvm::SmallSet<const Decl *, 16> &Callees) { |
| if (const auto *Call = dyn_cast<CallExpr>(StmtNode)) { |
| const Decl *Callee = Call->getDirectCallee(); |
| |
| if (!Callee) |
| return false; // unresolved call |
| Callees.insert(Callee->getCanonicalDecl()); |
| } |
| if (const auto *Call = dyn_cast<ObjCMessageExpr>(StmtNode)) { |
| const Decl *Callee = Call->getMethodDecl(); |
| |
| if (!Callee) |
| return false; // unresolved call |
| Callees.insert(Callee->getCanonicalDecl()); |
| } |
| for (const Stmt *Child : StmtNode->children()) |
| if (Child && !populateCallees(Child, Callees)) |
| return false; |
| return true; |
| } |
| |
| /// returns true iff `SCC` contains `Func` and its' function set overlaps with |
| /// `Callees` |
| static bool overlap(ArrayRef<CallGraphNode *> SCC, |
| const llvm::SmallSet<const Decl *, 16> &Callees, |
| const Decl *Func) { |
| bool ContainsFunc = false, Overlap = false; |
| |
| for (const CallGraphNode *GNode : SCC) { |
| const Decl *CanDecl = GNode->getDecl()->getCanonicalDecl(); |
| |
| ContainsFunc = ContainsFunc || (CanDecl == Func); |
| Overlap = Overlap || Callees.contains(CanDecl); |
| if (ContainsFunc && Overlap) |
| return true; |
| } |
| return false; |
| } |
| |
| /// returns true iff `Cond` involves at least one static local variable. |
| static bool hasStaticLocalVariable(const Stmt *Cond) { |
| if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) |
| if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) |
| if (VD->isStaticLocal()) |
| return true; |
| for (const Stmt *Child : Cond->children()) |
| if (Child && hasStaticLocalVariable(Child)) |
| return true; |
| return false; |
| } |
| |
| /// Tests if the loop condition `Cond` involves static local variables and |
| /// the enclosing function `Func` is recursive. |
| /// |
| /// \code |
| /// void f() { |
| /// static int i = 10; |
| /// i--; |
| /// while (i >= 0) f(); |
| /// } |
| /// \endcode |
| /// The example above is NOT an infinite loop. |
| static bool hasRecursionOverStaticLoopCondVariables(const Expr *Cond, |
| const Stmt *LoopStmt, |
| const Decl *Func, |
| const ASTContext *Ctx) { |
| if (!hasStaticLocalVariable(Cond)) |
| return false; |
| |
| llvm::SmallSet<const Decl *, 16> CalleesInLoop; |
| |
| if (!populateCallees(LoopStmt, CalleesInLoop)) { |
| // If there are unresolved indirect calls, we assume there could |
| // be recursion so to avoid false alarm. |
| return true; |
| } |
| if (CalleesInLoop.empty()) |
| return false; |
| |
| TranslationUnitDecl *TUDecl = Ctx->getTranslationUnitDecl(); |
| CallGraph CG; |
| |
| CG.addToCallGraph(TUDecl); |
| // For each `SCC` containing `Func`, if functions in the `SCC` |
| // overlap with `CalleesInLoop`, there is a recursive call in `LoopStmt`. |
| for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG), |
| SCCE = llvm::scc_end(&CG); |
| SCCI != SCCE; ++SCCI) { |
| if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes. |
| continue; |
| // `SCC`s are mutually disjoint, so there will be no redundancy in |
| // comparing `SCC` with the callee set one by one. |
| if (overlap(*SCCI, CalleesInLoop, Func->getCanonicalDecl())) |
| return true; |
| } |
| return false; |
| } |
| |
| void InfiniteLoopCheck::registerMatchers(MatchFinder *Finder) { |
| const auto LoopCondition = allOf( |
| hasCondition( |
| expr(forCallable(decl().bind("func"))).bind("condition")), |
| unless(hasBody(hasDescendant( |
| loopEndingStmt(forCallable(equalsBoundNode("func"))))))); |
| |
| Finder->addMatcher(mapAnyOf(whileStmt, doStmt, forStmt) |
| .with(LoopCondition) |
| .bind("loop-stmt"), |
| this); |
| } |
| |
| void InfiniteLoopCheck::check(const MatchFinder::MatchResult &Result) { |
| const auto *Cond = Result.Nodes.getNodeAs<Expr>("condition"); |
| const auto *LoopStmt = Result.Nodes.getNodeAs<Stmt>("loop-stmt"); |
| const auto *Func = Result.Nodes.getNodeAs<Decl>("func"); |
| |
| if (isKnownToHaveValue(*Cond, *Result.Context, false)) |
| return; |
| |
| bool ShouldHaveConditionVariables = true; |
| if (const auto *While = dyn_cast<WhileStmt>(LoopStmt)) { |
| if (const VarDecl *LoopVarDecl = While->getConditionVariable()) { |
| if (const Expr *Init = LoopVarDecl->getInit()) { |
| ShouldHaveConditionVariables = false; |
| Cond = Init; |
| } |
| } |
| } |
| |
| if (ExprMutationAnalyzer::isUnevaluated(LoopStmt, *LoopStmt, *Result.Context)) |
| return; |
| |
| if (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, Result.Context)) |
| return; |
| if (hasRecursionOverStaticLoopCondVariables(Cond, LoopStmt, Func, |
| Result.Context)) |
| return; |
| |
| std::string CondVarNames = getCondVarNames(Cond); |
| if (ShouldHaveConditionVariables && CondVarNames.empty()) |
| return; |
| |
| if (CondVarNames.empty()) { |
| diag(LoopStmt->getBeginLoc(), |
| "this loop is infinite; it does not check any variables in the" |
| " condition"); |
| } else { |
| diag(LoopStmt->getBeginLoc(), |
| "this loop is infinite; none of its condition variables (%0)" |
| " are updated in the loop body") |
| << CondVarNames; |
| } |
| } |
| |
| } // namespace tidy::bugprone |
| } // namespace clang |
