| //===--- 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" |
| |
| using namespace clang::ast_matchers; |
| using clang::tidy::utils::hasPtrOrReferenceInFunc; |
| |
| namespace clang { |
| namespace tidy { |
| namespace bugprone { |
| |
| static internal::Matcher<Stmt> |
| loopEndingStmt(internal::Matcher<Stmt> Internal) { |
| // FIXME: Cover noreturn ObjC methods (and blocks?). |
| return stmt(anyOf( |
| mapAnyOf(breakStmt, returnStmt, gotoStmt, cxxThrowExpr).with(Internal), |
| callExpr(Internal, callee(functionDecl(isNoReturn()))))); |
| } |
| |
| /// 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 isKnownFalse(const Expr &Cond, const ASTContext &Ctx) { |
| if (Cond.isValueDependent()) |
| return false; |
| bool Result = false; |
| if (Cond.EvaluateAsBooleanCondition(Result, Ctx)) |
| return !Result; |
| 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 (isKnownFalse(*Cond, *Result.Context)) |
| 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 (isAtLeastOneCondVarChanged(Func, LoopStmt, Cond, 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 bugprone |
| } // namespace tidy |
| } // namespace clang |