Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -172,6 +172,10 @@ HelpText<"Check for cases where the dynamic and the static type of an object are unrelated.">, DescFile<"DynamicTypeChecker.cpp">; +def RecursionChecker : Checker<"RecursionChecker">, + HelpText<"Check for cases of infinite recursion.">, + DescFile<"RecursionChecker.cpp">; + } // end "alpha.core" let ParentPackage = Nullability in { Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -38,6 +38,7 @@ FixedAddressChecker.cpp GenericTaintChecker.cpp IdenticalExprChecker.cpp + RecursionChecker.cpp IvarInvalidationChecker.cpp LLVMConventionsChecker.cpp LocalizationChecker.cpp Index: lib/StaticAnalyzer/Checkers/RecursionChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/RecursionChecker.cpp @@ -0,0 +1,157 @@ +// InfiniteRecursionChecker.cpp - Test if function is infinitely +// recursive--*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This defines TestAfterDivZeroChecker, a builtin check that performs checks +// for division by zero where the division occurs before comparison with zero. +// +//===----------------------------------------------------------------------===// + +#include "ClangSACheckers.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +REGISTER_SET_WITH_PROGRAMSTATE(DirtyStackFrames, const clang::StackFrameContext *) + +namespace { +using namespace clang; +using namespace ento; + +class RecursionChecker + : public Checker { + mutable std::unique_ptr BT; + + void emitReport(CheckerContext &C) const; + + bool compareArgs(CheckerContext &C, const ProgramStateRef &State, + const SVal &CurArg, const SVal &PrevArg) const; + +public: + void checkPreCall(const CallEvent &Call, CheckerContext &C) const; + + bool wantsRegionChangeUpdate(ProgramStateRef State, + const LocationContext *LCtx) const; + + ProgramStateRef + checkRegionChanges(ProgramStateRef State, + const InvalidatedSymbols *Invalidated, + ArrayRef ExplicitRegions, + ArrayRef Regions, const CallEvent *Call, + const LocationContext *LCtx) const; + void checkPostCall(const CallEvent &Call, + CheckerContext &C) const; +}; +} + + +void RecursionChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + + const FunctionDecl *CurFuncDecl = + dyn_cast_or_null(Call.getDecl()); + if (!CurFuncDecl) + return; + CurFuncDecl = CurFuncDecl->getCanonicalDecl(); + + const ProgramStateRef State = C.getState(); + + for (const auto *ParentLC = C.getStackFrame()->getParent(); + ParentLC != nullptr; ParentLC = ParentLC->getParent()) { + + if (ParentLC->getKind() != LocationContext::StackFrame) + continue; + + + const StackFrameContext *PrevStackFrameCtx = + ParentLC->getCurrentStackFrame(); + + if (State->contains(PrevStackFrameCtx)) + return; + + const FunctionDecl *PrevFuncDecl = + (const FunctionDecl *)PrevStackFrameCtx->getDecl(); + PrevFuncDecl = PrevFuncDecl->getCanonicalDecl(); + + if (PrevFuncDecl != CurFuncDecl) + continue; + + bool SameArgs = true; + for (unsigned i = 0; SameArgs && i < CurFuncDecl->getNumParams(); ++i) { + SVal CurArg = Call.getArgSVal(i); + SVal PrevArg = State->getArgSVal(PrevStackFrameCtx, i); + SameArgs = SameArgs && compareArgs(C, State, CurArg, PrevArg); + } + + if (SameArgs) + emitReport(C); + } +} +void RecursionChecker::checkPostCall(const CallEvent &Call, + CheckerContext &C) const { + ProgramStateRef State = C.getState(); + State->remove(C.getStackFrame()); +} +bool RecursionChecker::compareArgs(CheckerContext &C, + const ProgramStateRef &state, + const SVal &curArg, + const SVal &prevArg) const { + SValBuilder &sValBuilder = C.getSValBuilder(); + ConstraintManager &constraintManager = C.getConstraintManager(); + + SVal argsEqualSVal = sValBuilder.evalBinOp(state, BO_EQ, curArg, prevArg, + sValBuilder.getConditionType()); + Optional argsEqual = argsEqualSVal.getAs(); + + if (!argsEqual) + return false; + + ProgramStateRef stateEQ, stateNEQ; + std::tie(stateEQ, stateNEQ) = constraintManager.assumeDual(state, *argsEqual); + + if (stateNEQ) + return false; + + return true; +} + +bool RecursionChecker::wantsRegionChangeUpdate( + ProgramStateRef State, const LocationContext *LCtx) const { + return true; +} + +ProgramStateRef RecursionChecker::checkRegionChanges( + ProgramStateRef State, const InvalidatedSymbols *Invalidated, + ArrayRef ExplicitRegions, + ArrayRef Regions, const CallEvent *Call, + const LocationContext *LCtx) const { + State = State->add(LCtx->getCurrentStackFrame()); + for (const auto *ParentLC = LCtx->getCurrentStackFrame()->getParent(); + ParentLC != nullptr; ParentLC = ParentLC->getParent()) { + State = State->add(ParentLC->getCurrentStackFrame()); + } + return State; +} + +void RecursionChecker::emitReport(CheckerContext &C) const { + if (!BT) + BT.reset( + new BugType(this, "Infinite recursion detected", "RecursionChecker")); + + ExplodedNode *node = C.generateErrorNode(); + if (!node) + return; + + auto report = llvm::make_unique(*BT, BT->getName(), node); + C.emitReport(std::move(report)); +} + +void ento::registerRecursionChecker(CheckerManager &mgr) { + mgr.registerChecker(); +} Index: test/Analysis/misc-ps-region-store.cpp =================================================================== --- test/Analysis/misc-ps-region-store.cpp +++ test/Analysis/misc-ps-region-store.cpp @@ -617,7 +617,7 @@ void test_alloca_in_a_recursive_function(int p1) { __builtin_alloca (p1); - test_alloca_in_a_recursive_function(1); + test_alloca_in_a_recursive_function(1); // expected-warning {{Infinite recursion detected}} test_alloca_in_a_recursive_function(2); } Index: test/Analysis/recursion.cpp =================================================================== --- /dev/null +++ test/Analysis/recursion.cpp @@ -0,0 +1,210 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.core.RecursionChecker -verify %s + +namespace obvious { + +void f() { + f(); // expected-warning {{Infinite recursion detected}} +} + +void h(); + +// Mutual recursion - simplest case +void g() { + h(); // expected-warning {{Infinite recursion detected}} +} + +void h() { + g(); +} + +} + +namespace region_changes { + +// some global variable +int SampleGlobalVariable = 0; + +void f2(); +void f3(); +void f1(); + +void f1() { + f2(); +} + +// we spoil the frame here by touching global variable - no warnings +void f2() { + SampleGlobalVariable = 1; + f3(); +} + +// no warning because frame of f1 has been spoiled in f2! +void f3() { + f1(); +} + +void f() { + f1(); +} + +void f5(); +void f6(); +void f7(); +void f4(); + +void f5() { + f6(); +} + +void f6() { + f7(); +} + +void f7() { + f5(); // expected-warning {{Infinite recursion detected}} +} + +// only the first frame is spoiled, the two over it are fine +void f4() { + SampleGlobalVariable = 1; + f5(); +} + +} + +namespace obvious_with_arguments { + +void f(int a) { + f(a); // expected-warning {{Infinite recursion detected}} +} + +void h(int a, int b); + +void g(int a, int b) { + h(b, a); // expected-warning {{Infinite recursion detected}} +} + +void h(int a, int b) { + g(b, a); +} + +void f2(int a); + +void f1(int a, int b) { + f2(a); // expected-warning {{Infinite recursion detected}} +} + +void f2(int a) { + f1(a, 3); +} + +} + +namespace object_oriented { + +struct A { + void f() { + f(); // expected-warning {{Infinite recursion detected}} + } + + // Mutual recursion - simplest case + void g() { + h(); + } + + void h() { + g(); // expected-warning {{Infinite recursion detected}} + } + void f(int a) { + f(a); // expected-warning {{Infinite recursion detected}} + } + + void g1(int a, int b) { + h1(b, a); + } + + void h1(int a, int b) { + g1(b, a); // expected-warning {{Infinite recursion detected}} + } + + void f1(int a, int b) { + f2(a); + } + + void f2(int a) { + f1(a, 3); // expected-warning {{Infinite recursion detected}} + } + +}; + +void start1() { + A a; + a.f(); +} + +void start2() { + A a; + a.g(); +} + +void start3() { + A a; + a.g1(1, 2); +} + +void start4() { + A a; + a.f1(1, 3); +} + +class B { +public: + + int f(A& a) { + return f(a); // expected-warning {{Infinite recursion detected}} + } + + A g(A& a, int b) { + return h(b, a); + } + + A h(int a, A& b) { + return g(b, a); // expected-warning {{Infinite recursion detected}} + } + + int f1(const B& b) const { + return b.f1(*this); // expected-warning {{Infinite recursion detected}} + } + + void g1(const B& b) const { + b.h1(*this); + } + + void h1(const B& b) const { + b.g1(*this); // expected-warning {{Infinite recursion detected}} + } + +}; + +void start5() { + B b; + A a; + b.f(a); +} + +void start6() { + B b; + A a; + b.g(a, 3); +} + +void start7() { + B b1, b2; + b1.f1(b2); +} + +void start8() { + B b1, b2; + b1.g1(b2); +} +}