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,219 @@ +// RecursionChecker.cpp - Tests for infinitely recursive functions -*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This defines a checker that aims to find cases of infinite recursion +// by searching up the call stack. It is in alpha.core but will hopefully +// eventually move to core package. +// +//===----------------------------------------------------------------------===// + +#include "ClangSACheckers.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +// Stackframe is considered "dirty", when there was any kind of region change +// in it or in any function that was called from it. +// As you see below, the checker then stops the search down the stack once +// it encounters such a "dirty" frame. The reason for such behavior is that +// we can no longer be sure that conditions upon which the recursive call +// depends on did not change in an unpredictable way. The class of region changes +// that trigger this behavior will be more fine-grained in subsequent versions of +// this patch. +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; + + Optional getThisArgument(const CallEvent &Call) const; + + bool compareArgs(const SVal &curArg, + const SVal &prevArg, + CheckerContext &C) const; + + bool checkReceiversSame(const CallEvent &Call, + const StackFrameContext *SFC, + CheckerContext &C) const; + + bool checkThisPointersSame(const CallEvent &Call, + const StackFrameContext *SFC, + CheckerContext &C) const; + + bool checkAllArgumentsSame(const CallEvent &Call, + const StackFrameContext *SFC, + CheckerContext &C) const; + + void checkPreCallImpl(const CallEvent &Call, CheckerContext &C) const; + +public: + void checkPreCall(const CallEvent &Call, CheckerContext &C) const { + checkPreCallImpl(Call, C); + } + + void checkPreObjCMessage(const ObjCMethodCall &Msg, CheckerContext &C) const { + checkPreCallImpl(Msg, C); + } + + ProgramStateRef checkRegionChanges(ProgramStateRef State, + const InvalidatedSymbols *Invalidated, + ArrayRef ExplicitRegions, + ArrayRef Regions, + const LocationContext *LCtx, + const CallEvent *Call) const; + + void checkPostCall(const CallEvent &Call, CheckerContext &C) const; +}; +} + +ProgramStateRef RecursionChecker::checkRegionChanges( + ProgramStateRef State, const InvalidatedSymbols *Invalidated, + ArrayRef ExplicitRegions, + ArrayRef Regions, + const LocationContext *LCtx, + const CallEvent *Call) const { + + for (const auto *SFC = LCtx->getCurrentStackFrame(); + SFC != nullptr; + SFC = SFC->getParent()->getCurrentStackFrame()) + State = State->add(SFC); + + return State; +} + +void RecursionChecker::checkPostCall(const CallEvent &Call, + CheckerContext &C) const { + ProgramStateRef State = C.getState(); + State->remove(C.getStackFrame()); +} + +void RecursionChecker::checkPreCallImpl(const CallEvent &Call, + CheckerContext &C) const { + + for (const auto *SFC = C.getStackFrame(); + SFC != nullptr; + SFC = SFC->getParent()->getCurrentStackFrame()) { + if (C.getState()->contains(SFC)) + return; + + if (Call.getDecl() != SFC->getDecl()) + continue; + + if (isa(Call) && !checkReceiversSame(Call, SFC, C)) + continue; + else if (!checkThisPointersSame(Call, SFC, C)) + continue; + + if (checkAllArgumentsSame(Call, SFC, C)) + emitReport(C); + } +} + +inline bool +RecursionChecker::checkAllArgumentsSame(const CallEvent &Call, + const StackFrameContext *SFC, + CheckerContext &C) const { + bool SameArgs = true; + for (unsigned i = 0; SameArgs && i < Call.getNumArgs(); ++i) { + SVal CurArg = Call.getArgSVal(i); + SVal PrevArg = C.getState()->getArgSVal(SFC, i); + SameArgs = SameArgs && compareArgs(CurArg, PrevArg, C); + } + return SameArgs; +} + +inline bool +RecursionChecker::checkThisPointersSame(const CallEvent &Call, + const StackFrameContext *SFC, + CheckerContext &C) const { + const Optional CurThis = getThisArgument(Call); + const Optional PrevThis = C.getState()->getThisSVal(SFC); + + return !CurThis || compareArgs(*CurThis, *PrevThis, C); +} + +inline bool +RecursionChecker::checkReceiversSame(const CallEvent &Call, + const StackFrameContext *SFC, + CheckerContext &C) const { + const ObjCMethodCall *Msg_ = dyn_cast(&Call); + + const SVal CurReceiver = Msg_->getReceiverSVal(); + const Optional PrevReceiver = + C.getState()->getObjCMessageReceiverSVal(SFC); + + return PrevReceiver && *PrevReceiver == CurReceiver; +} + +inline void +RecursionChecker::emitReport(CheckerContext &C) const { + if (!BT) + BT.reset(new BugType(this, + "Infinite recursion detected", + categories::LogicError)); + + ExplodedNode *node = C.generateErrorNode(); + if (!node) + return; + + auto report = llvm::make_unique(*BT, BT->getName(), node); + C.emitReport(std::move(report)); +} + +inline Optional +RecursionChecker::getThisArgument(const CallEvent &Call) const { + const FunctionDecl *F = dyn_cast(Call.getDecl()); + if (!F) + return None; + F = F->getCanonicalDecl(); + + Optional CurThis; + if (isa(F)) + CurThis = cast(&Call)->getCXXThisVal(); + else if (isa(F)) + CurThis = cast(&Call)->getCXXThisVal(); + else if (isa(F)) + CurThis = cast(&Call)->getCXXThisVal(); + + return CurThis; +} + +inline bool +RecursionChecker::compareArgs(const SVal &curArg, + const SVal &prevArg, + CheckerContext &C) const { + const ProgramStateRef state = C.getState(); + 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); + + return !stateNEQ; +} + +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,246 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.core.RecursionChecker -verify %s + +namespace obvious { + +void simplestRecursiveFunction() { + simplestRecursiveFunction(); // expected-warning {{Infinite recursion detected}} +} + + +void simplestMutuallyRecursiveFunction2(); + +void simplestMutuallyRecursiveFunction1() { + simplestMutuallyRecursiveFunction2(); +} + +void simplestMutuallyRecursiveFunction2() { + simplestMutuallyRecursiveFunction1(); // expected-warning {{Infinite recursion detected}} +} + +void startMutualRecursionTest() { + simplestMutuallyRecursiveFunction1(); +} + +} + +namespace region_changes { + +// some global variable +int SampleGlobalVariable = 0; + +void firstInNoWarnCycle(); +void secondInNoWarnCycle(); +void thirdInNoWarnCycle(); + +void firstInNoWarnCycle() { + secondInNoWarnCycle(); +} + +// we spoil the frame here by touching global variable - no warnings +void secondInNoWarnCycle() { + if (++SampleGlobalVariable) + thirdInNoWarnCycle(); +} + +// no warning because frame of f1 has been spoiled in f2! +void thirdInNoWarnCycle() { + firstInNoWarnCycle(); +} + +void startNoWarnCycle() { + firstInNoWarnCycle(); +} + + +void firstInWarnCycle(); +void secondInWarnCycle(); +void thirdInWarnCycle(); +void fourthInWarnCycle(); + +void secondInWarnCycle() { + thirdInWarnCycle(); +} + +void thirdInWarnCycle() { + fourthInWarnCycle(); +} + +void fourthInWarnCycle() { + secondInWarnCycle(); // expected-warning {{Infinite recursion detected}} +} + +// only the first frame is spoiled, the two over it are fine +void firstInWarnCycle() { + SampleGlobalVariable = 1; + if (SampleGlobalVariable++ < 5) + secondInWarnCycle(); +} + +} + +namespace obvious_with_arguments { + +void oneClassArgFunction(int a) { + oneClassArgFunction(a); // expected-warning {{Infinite recursion detected}} +} + +void twoArgsSecondMutuallyRecursiveFunction(int a, int b); + +void twoArgsMutuallyRecursiveFunction(int a, int b) { + twoArgsSecondMutuallyRecursiveFunction(b, a); +} + +void twoArgsSecondMutuallyRecursiveFunction(int a, int b) { + twoArgsMutuallyRecursiveFunction(b, a); // expected-warning {{Infinite recursion detected}} +} + +void startMutuallyRecursiveCycle() { + twoArgsMutuallyRecursiveFunction(1, 2); +} + + +// Making sure the number of parameters doesn't cause problems for the checker +void oneArgFunction(int a); + +void twoArgsFunction(int a, int b) { + oneArgFunction(a); +} + +void oneArgFunction(int a) { + twoArgsFunction(a, 3); // expected-warning {{Infinite recursion detected}} +} + +void startVariableClassArgNumberCycle() { + oneArgFunction(1); +} + + +bool onlyForwardDecl(); + +// we don't know anything about onlyForwardDecl so the RegionChanges callbacks +// ensure we don't rely on it to decide if the recursive call will happen +void recursiveFunctionUsingForwardDecl() { + if (!onlyForwardDecl()) + recursiveFunctionUsingForwardDecl(); +} + +} + +namespace object_oriented { + +struct ClassA { + void selfRecursiveMethod() { + selfRecursiveMethod(); // expected-warning {{Infinite recursion detected}} + } + + // Mutual recursion - simplest case + void mutuallyRecursiveMethod() { + anotherMutuallyRecursiveMethod(); + } + + void anotherMutuallyRecursiveMethod() { + mutuallyRecursiveMethod(); // expected-warning {{Infinite recursion detected}} + } + void methodWithArg(int a) { + methodWithArg(a); // expected-warning {{Infinite recursion detected}} + } + + void twoArgsMutuallyRecursive(int a, int b) { + anotherTwoArgsMutuallyRecursive(b, a); + } + + void anotherTwoArgsMutuallyRecursive(int a, int b) { + twoArgsMutuallyRecursive(b, a); // expected-warning {{Infinite recursion detected}} + } + + // different number arguments in mutually recursive methods + void twoArgsCallingOneArgsMethod(int a, int b) { + oneArgMethodCallingTwoArgsMethod(a); + } + + void oneArgMethodCallingTwoArgsMethod(int a) { + twoArgsCallingOneArgsMethod(a, 3); // expected-warning {{Infinite recursion detected}} + } + +}; + +void startSelfRecursiveMethod() { + ClassA a; + a.selfRecursiveMethod(); +} + +void startMutuallyRecursiveMethodCycle() { + ClassA a; + a.mutuallyRecursiveMethod(); +} + +void startMethodWithArg() { + ClassA a; + a.methodWithArg(1); +} + +void startTwoArgsMutuallyRecursiveCycle() { + ClassA a; + a.twoArgsMutuallyRecursive(1, 2); +} + +void start() { + ClassA a; + a.twoArgsCallingOneArgsMethod(1, 3); +} + +class ClassB { +public: + + int methodTakingObjectParam(ClassA& a) { + return methodTakingObjectParam(a); // expected-warning {{Infinite recursion detected}} + } + + + ClassA multiArgObjectTakingMutuallyRecursive(ClassA& a, int b) { + return anotherMultiArgObjectTakingMutuallyRecursive(b, a); + } + + ClassA anotherMultiArgObjectTakingMutuallyRecursive(int a, ClassA& b) { + return multiArgObjectTakingMutuallyRecursive(b, a); // expected-warning {{Infinite recursion detected}} + } + + + int recursiveWithDifferentThisPointer(const ClassB& b) const { + return b.recursiveWithDifferentThisPointer(*this); // expected-warning {{Infinite recursion detected}} + } + + + void mutuallyRecursiveWithDifferentThisPointer(const ClassB& b) const { + b.anotherMutuallyRecursiveWithDifferentThisPointer(*this); + } + + void anotherMutuallyRecursiveWithDifferentThisPointer(const ClassB& b) const { + b.mutuallyRecursiveWithDifferentThisPointer(*this); // expected-warning {{Infinite recursion detected}} + } + +}; + +void startMethodTakingObjectParam() { + ClassB b; + ClassA a; + b.methodTakingObjectParam(a); +} + +void startMultiArgObjectTakingMutuallyRecursive() { + ClassB b; + ClassA a; + b.multiArgObjectTakingMutuallyRecursive(a, 3); +} + +void startRecursiveWithDifferentThisPointer() { + ClassB b1, b2; + b1.recursiveWithDifferentThisPointer(b2); +} + +void startMutuallyRecursiveWithDifferentThisPointer() { + ClassB b1, b2; + b1.mutuallyRecursiveWithDifferentThisPointer(b2); +} + +}