k-wisniewski created this revision.
k-wisniewski added reviewers: zaks.anna, dcoughlin, NoQ, a.sidorin.
k-wisniewski added a subscriber: cfe-commits.
Herald added a subscriber: mgorny.
This patch adds RecursionChecker for finding infinite recursion. I have
refactored the checker quite thoroughly since the last time I posted it - it
should now support ObjC methods as well. I have fixed several issues pointed
out in the previous version too. My plan for now is to have it tested on some
real code bases to check how useful it is in practice and evaluate its
performance. I will also implement some heurestics to eliminate excesive false
positives/negatives and evaluate them.
BTW. as I'm a complete newbie in Objective-C - could you please help me with
some interesting unit test cases for this checker?
Thanks in advance!
https://reviews.llvm.org/D27092
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/RecursionChecker.cpp
test/Analysis/misc-ps-region-store.cpp
test/Analysis/recursion.cpp
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);
+}
+
+}
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: 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<check::PreCall,
+ check::PreObjCMessage,
+ check::RegionChanges,
+ check::PostCall> {
+ mutable std::unique_ptr<BugType> BT;
+
+ void emitReport(CheckerContext &C) const;
+
+ Optional<SVal> 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<const MemRegion *> ExplicitRegions,
+ ArrayRef<const MemRegion *> 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<const MemRegion *> ExplicitRegions,
+ ArrayRef<const MemRegion *> Regions,
+ const LocationContext *LCtx,
+ const CallEvent *Call) const {
+
+ for (const auto *SFC = LCtx->getCurrentStackFrame();
+ SFC != nullptr;
+ SFC = SFC->getParent()->getCurrentStackFrame())
+ State = State->add<DirtyStackFrames>(SFC);
+
+ return State;
+}
+
+void RecursionChecker::checkPostCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ ProgramStateRef State = C.getState();
+ State->remove<DirtyStackFrames>(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<DirtyStackFrames>(SFC))
+ return;
+
+ if (Call.getDecl() != SFC->getDecl())
+ continue;
+
+ if (isa<ObjCMethodCall>(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<SVal> CurThis = getThisArgument(Call);
+ const Optional<SVal> 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<const ObjCMethodCall>(&Call);
+
+ const SVal CurReceiver = Msg_->getReceiverSVal();
+ const Optional<SVal> 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<BugReport>(*BT, BT->getName(), node);
+ C.emitReport(std::move(report));
+}
+
+inline Optional<SVal>
+RecursionChecker::getThisArgument(const CallEvent &Call) const {
+ const FunctionDecl *F = dyn_cast<FunctionDecl>(Call.getDecl());
+ if (!F)
+ return None;
+ F = F->getCanonicalDecl();
+
+ Optional<SVal> CurThis;
+ if (isa<CXXMethodDecl>(F))
+ CurThis = cast<CXXInstanceCall>(&Call)->getCXXThisVal();
+ else if (isa<CXXConstructorDecl>(F))
+ CurThis = cast<CXXConstructorCall>(&Call)->getCXXThisVal();
+ else if (isa<CXXDestructorDecl>(F))
+ CurThis = cast<CXXDestructorCall>(&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<DefinedSVal> argsEqual = argsEqualSVal.getAs<DefinedSVal>();
+
+ if (!argsEqual)
+ return false;
+
+ ProgramStateRef stateEQ, stateNEQ;
+ std::tie(stateEQ, stateNEQ) = constraintManager.assumeDual(state, *argsEqual);
+
+ return !stateNEQ;
+}
+
+void ento::registerRecursionChecker(CheckerManager &mgr) {
+ mgr.registerChecker<RecursionChecker>();
+}
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: 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 {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
