Page MenuHomePhabricator

Add static analyzer checker for finding infinite recursion
AbandonedPublic

Authored by NoQ on Nov 13 2016, 8:01 AM.

Details

Summary

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.

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!

Diff Detail

Event Timeline

k-wisniewski retitled this revision from to Add static analyzer checker for finding infinite recursion.
k-wisniewski updated this object.
k-wisniewski added a subscriber: cfe-commits.

Wow, thank you for such a contribution! Did you evaluate this checker on some real code?

I have some minor inline comments below.

lib/StaticAnalyzer/Checkers/CMakeLists.txt
41

Please fix indentation here

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp
12

This description is for other checker, could you update it?

21

The idea of "dirty stack frames" deserves some explanation. As I understand, it describes function calls where some values may change unexpectedly and we cannot consider this calls later. Am I understanding correctly?

49

Incorrect indentation.

68

We may just use getParent()->getCurrentStackFrame() in the loop increment to make the code cleaner. What do you think?

79

We usually prefer LLVM [dyn_]cast<> where possible.

89

Maybe we can use early return here?

test/Analysis/recursion.cpp
27

I'd like to see some more informative function names: for me, it is hard to distinguish between f1-7 here :) It is also hard to determine the function where test starts.

@a.sidorin
Thank you for your review! I'll upload the new patch this evening that will include fixes for the things you pointed out. Can I also add you as a reviewer? Also: Can you have a look at my other patch that I have linked in the description? Thanks in advance!

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp
12

Sure, it was easier for me to use some other checker as a template and I forgot about it. Should I add you as a reviewer once I upload the updated patch?

21

Yes! Right now it considers frame as "dirty" when there was any kind of region change in this frame or in any function that was called from it. As you see below, it then stops the search down the stack once it encounter such a "dirty" frame, because it can no longer be sure that conditions upon which the recursive call depends on did not change in an unpredictable way. It's obviously too broad a definition and in the next iterations I'll try to narrow it down to variables that affect whether the recursive call happens or not. I also consider looking at the way it changes to determine if it's meaningful or not.

test/Analysis/recursion.cpp
27

The convention I know is that the bottom-most one gets considered first, but I may add some explicitly marked entry points for the sake of consistency and to make it easier to reason about.

NoQ added a subscriber: NoQ.Nov 14 2016, 8:27 AM
NoQ added a comment.Nov 14 2016, 11:37 AM

Thank you for working on this! The overall approach is good. Because alpha checkers are disabled by default, false positives can be addressed later in subsequent commits.

lib/StaticAnalyzer/Checkers/RecursionChecker.cpp
2

Accidental line break :o

21

I think this deserves commenting, at least the very mechanism of how a stack frame is considered dirty (if it is present in the set, or if a parent is present in the set, or something else, and why is the chosen method somehow correct).

145

I think one of the builtin bugtypes should be used, such as LogicError. In any case, both of these should be human-friendly (they appear eg. in scan-view).

test/Analysis/recursion.cpp
27

There's a way to hard-check this through FileCheck + -analyzer-display-progress (see inlining/analysis-order.c). Might be an overkill, but on the other hand may actually improve readability of the test quite a bit.

37

This should eventually warn. Even though the variable is accessed, it's not really changed :)

I'd suggest something like:

++SampleGlobalVariable;
if (SampleGlobalVariable < 100)
  f3();

It'd make sure that the test is "correct" (it's obvious to the reader that this is a false positive we'd never want to warn about). But you could also keep the original test with a FIXME remark ("we should eventually warn about this").

I also think that this group of tests deserves to have the following test:

bool bar(); // no definition!
void foo() {
  if (bar()) { // may change the global state
    foo(); // no-warning
  }
}

This test case should magically work because calling bar() will change the "global memory space" region (invalidate all globals).

NoQ added inline comments.Nov 18 2016, 5:30 PM
lib/StaticAnalyzer/Checkers/RecursionChecker.cpp
65

Off-by-1: C.getStackFrame() is already the caller context, which we should check.

NoQ commandeered this revision.Nov 30 2016, 12:00 AM
NoQ added a reviewer: k-wisniewski.

Seems to become outdated with D27092.

NoQ abandoned this revision.Nov 30 2016, 12:01 AM
NoQ marked 8 inline comments as done.