k-wisniewski created this revision.
k-wisniewski added reviewers: zaks.anna, dcoughlin, dergachev.a.
k-wisniewski added a subscriber: cfe-commits.
Herald added a subscriber: mgorny.
This is the very first version of a checker that aims to find cases of infinite
recursion. It relies on Add LocationContext to members of check::RegionChanges
<https://reviews.llvm.org/D26588>.
What it does:
- it registers on check::PreCall and check::RegionChanges events
- in checkPreCall digs through the call stack searching for invocation of
currently encountered function/method with exactly the same arguments (meaning
same SVals of them)
- in checkRegionChanges makes all the frames on the call stack invalid by
adding them to the set of dirty frames
- if the frame encountered by the search in checkPreCall is in the set of dirty
frames the search stops
Obviously this has lots of both false negatives and false positives, but I plan
to improve it by decreasing the number of frame invalidations and only taking
into account changes that affect whether the recursive call happens or not. The
support for Obj-C method calls is also on the way.
I welcome any ideas on how to make it better!
PS. This is one of my first patches submitted here - sorry if it doesn't comply
with some conventions you might have here!
https://reviews.llvm.org/D26589
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,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);
+}
+}
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,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<check::PreCall, check::RegionChanges, check::PostCall> {
+ mutable std::unique_ptr<BugType> 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<const MemRegion *> ExplicitRegions,
+ ArrayRef<const MemRegion *> 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<FunctionDecl>(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<DirtyStackFrames>(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<DirtyStackFrames>(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<DefinedSVal> argsEqual = argsEqualSVal.getAs<DefinedSVal>();
+
+ 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<const MemRegion *> ExplicitRegions,
+ ArrayRef<const MemRegion *> Regions, const CallEvent *Call,
+ const LocationContext *LCtx) const {
+ State = State->add<DirtyStackFrames>(LCtx->getCurrentStackFrame());
+ for (const auto *ParentLC = LCtx->getCurrentStackFrame()->getParent();
+ ParentLC != nullptr; ParentLC = ParentLC->getParent()) {
+ State = State->add<DirtyStackFrames>(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<BugReport>(*BT, BT->getName(), node);
+ C.emitReport(std::move(report));
+}
+
+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
