[analyzer][NFCI] Allow clients of NoStateChangeFuncVisitor to check entire function calls, rather than each ExplodedNode in it

[Szelethus]

Summary

D105553 added NoStateChangeFuncVisitor, an abstract class to aid in creating notes such as "Returning without writing to 'x'", or "Returning without changing the ownership status of allocated memory". Its clients need to define, among other things, what a change of state is.

For code like this:

f() {
  g();
}

foo() {
  f();
  h();
}

We'd have a path in the ExplodedGraph that looks like this:

             -- <g> -->
            /          \       
         ---     <f>    -------->        --- <h> --->
        /                        \      /            \
--------        <foo>             ------    <foo>     -->

When we're interested in whether f neglected to change some property, NoStateChangeFuncVisitor asks these questions:

                       ÷×~     
                -- <g> -->
           ß   /          \$    @&#*       
            ---     <f>    -------->        --- <h> --->
           /                        \      /            \
   --------        <foo>             ------    <foo>     -->

                           
Has anything changed in between # and *?
Has anything changed in between & and *?
Has anything changed in between @ and *?
...
Has anything changed in between $ and *?
Has anything changed in between × and ~?
Has anything changed in between ÷ and ~?
...
Has anything changed in between ß and *?
...

This is a rather thorough line of questioning, which is why in D105819, I was only interested in whether state *right before* and *right after* a function call changed, and early returned to the CallEnter location:

if (!CurrN->getLocationAs<CallEnter>())
  return;

Except that I made a typo, and forgot to negate the condition. So, in this patch, I'm fixing that, and under the same hood allow all clients to decide to do this whole-function check instead of the thorough one.

[Szelethus]

I also added new dump methods -- I had a trouble before realizing that CallEnter's stack frame is actually the *caller's*, not the *callee's* stack frame. Changes in findModifyingFrames aim to make the function more readable, and make sure that the correct stack frame will be marked as modifying.

[NoQ]

Would this work correctly when the property is changed but then reverted to its original state? This probably can't happen to MallocChecker (what has been freed cannot be unfreed) but it may happen to eg. PthreadLockChecker or to, well, Stores. In such cases it would be incorrect to say "returning without changing the state".

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

370

This is the right successor because we're in a heavily trimmed exploded graph, right?

[Szelethus]

In D108695#2967540, @NoQ wrote:

Would this work correctly when the property is changed but then reverted to its original state? This probably can't happen to MallocChecker (what has been freed cannot be unfreed) but it may happen to eg. PthreadLockChecker or to, well, Stores. In such cases it would be incorrect to say "returning without changing the state".

It should! But you have a point, I don't have the code to prove it right away. Maybe if I factored out the symbol part into NoStateChangeToSymbolVisitor, as teased in D105553#2864318, it'd have an easier time to see it. With that said, I don't currently see how the current implementation would be faulty, but even if it is, the patch adds an option, and doesn't the take old one (that NoStoreFuncVisitor still uses) away.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

370

Should be, yes.

[NoQ]

In D108695#2967885, @Szelethus wrote:

It should! But you have a point, I don't have the code to prove it right away. Maybe if I factored out the symbol part into NoStateChangeToSymbolVisitor, as teased in D105553#2864318, it'd have an easier time to see it. With that said, I don't currently see how the current implementation would be faulty, but even if it is, the patch adds an option, and doesn't the take old one (that NoStoreFuncVisitor still uses) away.

I mean, your implementation of findModifyingFrames() mostly boils down to:

return CallEnterN->getState()->get<State>(X) !=
     CallExitEndN->getState()->get<State>(X);

So if, say, X is a mutex and we're wondering whether it was unlocked in the function, but in reality it was unlocked and immediately locked again, then the above test would say "not modified" and you can't notice that it was modified temporarily without scanning all intermediate nodes. So if your note needs to make a distinction between "was not touched" and "was touched but reverted" you'll still need to do it the old way. I think this should be documented loudly in the comments.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

369

Wait, no, I don't think this test is sufficient. You may run into a CallExitEnd of a nested stack frame before you reach the CallExitEnd of the stack frame in question:

-> CallEnter foo()       --->
  -> CallEnter bar()        |
  <- CallExitEnd bar()      <--- ???
<- CallExitEnd foo()

[martong]

Nice work!

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

361

Why don't we add the stack frame here to FramesModifyingCalculated as well? If we are in a nested stack frame and we step back to a parent then it would be redundant to do the calculation again for the parent.

Ahh, to be honest, I think the idea of having both FramesModifying and FramesModifyingCalculated separated is prone to errors.
Why don't we have a simple map<StackFramContext, bool> with the boolean true meaning that the frame is modifying? And if the frame is not in the map that means it had never been calculated before.

370

Would it make sense to assert that there are no more than one successor ?

386

Using a for could simplify this loop and would eliminate the need to have a redundant loop variable bump both at line 420 and at 393.

[martong]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

675

You have no such parameter. But I guess we can get that from either of them.

[Szelethus]

• Make sure that the matching CallExitEnd is retrieved.
• Add a unit test to neatly demonstrate how the visitor is intended to be used.
• Fix the rest of the nits.

[Szelethus]

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

361

Yes, its stupid, but its just the one thing I didn't want to bother myself with. Though I agree it'd be better to drop these sets for something a lot more elegant. Btw mind that we insert into the calculated set each time we enter a new stack frame.

I'll leave a TODO, if you don't mind.

369

Good point. Added a bunch of asserts and changed to code to both retrieve, and ensure that the correct node is retrieved.

[Szelethus]

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

683–685

Whoops, this is wildly incorrect. Gotta fix that. The inlined function's stack frame is retrievable from the CallEnters first successor, or CallExitEnds first predecessor.

[martong]

Thanks! My concerns are addressed, looks good to me!

[thakis]

This seems to break tests: http://45.33.8.238/linux/54991/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[paquette]

I just reverted this again because of a bot failure here:

https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/23380/consoleFull

Please fix and recommit!

[uabelho]

Hi @Szelethus
A couple of tests fail for me on trunk with this patch:

Failed Tests (3):
  Clang-Unit :: StaticAnalyzer/./StaticAnalysisTests/FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeDueToRefinedConstraintNoReport
  Clang-Unit :: StaticAnalyzer/./StaticAnalysisTests/FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
  Clang-Unit :: StaticAnalyzer/./StaticAnalysisTests/FalsePositiveRefutationBRVisitorTestBase.UnSatInTheMiddleNoReport

Details from one failure below:

seroius03977 [12:05] [uabelho/master-github/llvm] -> /repo/uabelho/master-github/llvm/build-all/tools/clang/unittests/StaticAnalyzer/./StaticAnalysisTests --gtest_filter=FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
Note: Google Test filter = FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from FalsePositiveRefutationBRVisitorTestBase
[ RUN      ] FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
UnSatAtErrorNodeWithNewSymbolNoReport.cc:8:7: warning: REACHED_WITH_NO_CONTRADICTION [test.FalsePositiveGenerator]
      reachedWithNoContradiction();
      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 warning generated.
/repo/uabelho/master-github/clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp:162: Failure
Expected equality of these values:
  Diags
    Which is: "test.FalsePositiveGenerator: Assuming the condition is false | REACHED_WITH_NO_CONTRADICTION\n"
  "test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION\n"
UnSatAtErrorNodeWithNewSymbolNoReport.cc:8:7: warning: REACHED_WITH_NO_CONTRADICTION [test.FalsePositiveGenerator]
      reachedWithNoContradiction();
      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
UnSatAtErrorNodeWithNewSymbolNoReport.cc:9:7: warning: CAN_BE_TRUE [test.FalsePositiveGenerator]
      reportIfCanBeTrue(x == 0); // contradiction
      ^~~~~~~~~~~~~~~~~~~~~~~~~
2 warnings generated.
/repo/uabelho/master-github/clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp:171: Failure
Expected equality of these values:
  Diags2
    Which is: "test.FalsePositiveGenerator: Assuming the condition is false | REACHED_WITH_NO_CONTRADICTION\ntest.FalsePositiveGenerator: Assuming the condition is false | CAN_BE_TRUE\n"
  "test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION\n" "test.FalsePositiveGenerator: CAN_BE_TRUE\n"
    Which is: "test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION\ntest.FalsePositiveGenerator: CAN_BE_TRUE\n"
With diff:
@@ -1,2 +1,2 @@
-test.FalsePositiveGenerator: Assuming the condition is false | REACHED_WITH_NO_CONTRADICTION
-test.FalsePositiveGenerator: Assuming the condition is false | CAN_BE_TRUE\n
+test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION
+test.FalsePositiveGenerator: CAN_BE_TRUE\n

[  FAILED  ] FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport (41 ms)
[----------] 1 test from FalsePositiveRefutationBRVisitorTestBase (41 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (42 ms total)
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport

 1 FAILED TEST

[Szelethus]

I'll attend to this ASAP. Thanks for the heads up!

[steakhal]

In D108695#2999378, @uabelho wrote:

Hi @Szelethus
A couple of tests fail for me on trunk with this patch

Uh, that's my unittest :D
I suspect you are running some sort of CI where you set up Z3.

I suspect we should slightly modify the expected output then.

[uabelho]

In D108695#2999432, @steakhal wrote:

In D108695#2999378, @uabelho wrote:

Hi @Szelethus
A couple of tests fail for me on trunk with this patch

Uh, that's my unittest :D
I suspect you are running some sort of CI where you set up Z3.

Yes, I have Z3 enabled.

[Szelethus]

rGfb4d590a622f4031900516360c07ee6ace01c5e6 should sort this out!

[uabelho]

In D108695#2999677, @Szelethus wrote:

rGfb4d590a622f4031900516360c07ee6ace01c5e6 should sort this out!

Yes now it works.
Thank you!

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

private:
   llvm::SmallPtrSet<const StackFrameContext *, 32> FramesModifying;
   llvm::SmallPtrSet<const StackFrameContext *, 32> FramesModifyingCalculated;
 
   /// Check and lazily calculate whether the state is modified in the stack
   /// frame to which \p CallExitBeginN belongs.
   /// The calculation is cached in FramesModifying.
   bool isModifiedInFrame(const ExplodedNode *CallExitBeginN);
 
+  void markFrameAsModifying(const StackFrameContext *SCtx);
+
   /// Write to \c FramesModifying all stack frames along the path in the current
   /// stack frame which modifies the state.
   void findModifyingFrames(const ExplodedNode *const CallExitBeginN);
 
 protected:
   bugreporter::TrackingKind TKind;
 
-  /// \return Whether the state was modified from the current node, \CurrN, to
-  /// the end of the stack fram, at \p CallExitBeginN.
+  /// \return Whether the state was modified from the current node, \p CurrN, to
+  /// the end of the stack fram, at \p CallExitBeginN. \p CurrN and
+  /// \p CallExitBeginN are always in the same stack frame.
   virtual bool
   wasModifiedBeforeCallExit(const ExplodedNode *CurrN,
-                            const ExplodedNode *CallExitBeginN) = 0;
+                            const ExplodedNode *CallExitBeginN) {
+    return false;
+  }
+
+  /// \return Whether the state was modified in the inlined function call in
+  /// between \p CallEnterN and \p CallExitBeginN. Mind that the stack frame
+  /// retrieved from a CallEnter is the *caller's* stack frame! The inlined
+  /// function's stack should be retrieved from \p CallExitBeginN.
+  virtual bool wasModifiedInFunction(const ExplodedNode *CallEnterN,
+                                     const ExplodedNode *CallExitEndN) {
+    return false;
+  }
 
   /// Consume the information on the non-modifying stack frame in order to
   /// either emit a note or not. May suppress the report entirely.
   /// \return Diagnostics piece for the unmodified state in the current
   /// function, if it decides to emit one. A good description might start with
   /// "Returning without...".
   virtual PathDiagnosticPieceRef
   maybeEmitNoteForObjCSelf(PathSensitiveBugReport &R,
                            const ObjCMethodCall &Call,
                            const ExplodedNode *N) = 0;
 
   /// Consume the information on the non-modifying stack frame in order to
   /// either emit a note or not. May suppress the report entirely.
   /// \return Diagnostics piece for the unmodified state in the current

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

 #include "AllocationState.h"
 #include "InterCheckerAPI.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/ParentMap.h"
+#include "clang/Analysis/ProgramPoint.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
 #include <climits>
 #include <functional>
 #include <utility>
 
 using namespace clang;
 using namespace ento;
 using namespace std::placeholders;
 
OwnershipBindingsHandler(SymbolRef Sym, OwnerSet &Owners)
         : Sym(Sym), Owners(Owners) {}
 
     bool HandleBinding(StoreManager &SMgr, Store Store, const MemRegion *Region,
                        SVal Val) override {
       if (Val.getAsSymbol() == Sym)
         Owners.insert(Region);
       return true;
     }
+
+    LLVM_DUMP_METHOD void dump() const { dumpToStream(llvm::errs()); }
+    LLVM_DUMP_METHOD void dumpToStream(llvm::raw_ostream &out) const {
+      out << "Owners: {\n";
+      for (const MemRegion *Owner : Owners) {
+        out << "  ";
+        Owner->dumpToStream(out);
+        out << ",\n";
+      }
+      out << "}\n";
+    }
   };
 
 protected:
   OwnerSet getOwnersAtNode(const ExplodedNode *N) {
     OwnerSet Ret;
 
     ProgramStateRef State = N->getState();
     OwnershipBindingsHandler Handler{Sym, Ret};
     State->getStateManager().getStoreManager().iterBindings(State->getStore(),
                                                             Handler);
     return Ret;
   }
 
-  static const ExplodedNode *getCallExitEnd(const ExplodedNode *N) {
-    while (N && !N->getLocationAs<CallExitEnd>())
-      N = N->getFirstSucc();
-    return N;
+  LLVM_DUMP_METHOD static std::string
+  getFunctionName(const ExplodedNode *CallEnterN) {
+    if (const CallExpr *CE = llvm::dyn_cast_or_null<CallExpr>(
+            CallEnterN->getLocationAs<CallEnter>()->getCallExpr()))
+      if (const FunctionDecl *FD = CE->getDirectCallee())
+        return FD->getQualifiedNameAsString();
+    return "";
   }
 
   virtual bool
-  wasModifiedBeforeCallExit(const ExplodedNode *CurrN,
-                            const ExplodedNode *CallExitN) override {
-    if (CurrN->getLocationAs<CallEnter>())
-      return true;
-
-    // Its the state right *after* the call that is interesting. Any pointers
-    // inside the call that pointed to the allocated memory are of little
-    // consequence if their lifetime ends within the function.
-    CallExitN = getCallExitEnd(CallExitN);
-    if (!CallExitN)
-      return true;
-
+  wasModifiedInFunction(const ExplodedNode *CurrN,
+                        const ExplodedNode *CallExitEndN) override {
     if (CurrN->getState()->get<RegionState>(Sym) !=
-        CallExitN->getState()->get<RegionState>(Sym))
+        CallExitEndN->getState()->get<RegionState>(Sym))
       return true;
 
     OwnerSet CurrOwners = getOwnersAtNode(CurrN);
-    OwnerSet ExitOwners = getOwnersAtNode(CallExitN);
+    OwnerSet ExitOwners = getOwnersAtNode(CallExitEndN);
 
     // Owners in the current set may be purged from the analyzer later on.
     // If a variable is dead (is not referenced directly or indirectly after
     // some point), it will be removed from the Store before the end of its
     // actual lifetime.
     // This means that that if the ownership status didn't change, CurrOwners
     // must be a superset of, but not necessarily equal to ExitOwners.
     return !llvm::set_is_subset(ExitOwners, CurrOwners);

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

 bool NoStateChangeFuncVisitor::isModifiedInFrame(const ExplodedNode *N) {
   const LocationContext *Ctx = N->getLocationContext();
   const StackFrameContext *SCtx = Ctx->getStackFrame();
   if (!FramesModifyingCalculated.count(SCtx))
     findModifyingFrames(N);
   return FramesModifying.count(SCtx);
 }
 
+void NoStateChangeFuncVisitor::markFrameAsModifying(
+    const StackFrameContext *SCtx) {
+  while (!SCtx->inTopFrame()) {
+    auto p = FramesModifying.insert(SCtx);
+    if (!p.second)
+      break; // Frame and all its parents already inserted.
+    SCtx = SCtx->getParent()->getStackFrame();
+  }
+}
+
+static const ExplodedNode *getCallExitEnd(const ExplodedNode *N) {
+  while (N && !N->getLocationAs<CallExitEnd>())
+    N = N->getFirstSucc();
+  return N;
+}
+
 void NoStateChangeFuncVisitor::findModifyingFrames(
     const ExplodedNode *const CallExitBeginN) {
 
   assert(CallExitBeginN->getLocationAs<CallExitBegin>());
-  const ExplodedNode *LastReturnN = CallExitBeginN;
+
   const StackFrameContext *const OriginalSCtx =
       CallExitBeginN->getLocationContext()->getStackFrame();
 
   const ExplodedNode *CurrN = CallExitBeginN;
+  const ExplodedNode *CurrCallExitBeginN = CallExitBeginN;
+  const StackFrameContext *CurrentSCtx = OriginalSCtx;
 
-  do {
-    ProgramStateRef State = CurrN->getState();
-    auto CallExitLoc = CurrN->getLocationAs<CallExitBegin>();
-    if (CallExitLoc) {
-      LastReturnN = CurrN;
+  while (CurrN) {
+    // Found a new inlined call.
+    if (CurrN->getLocationAs<CallExitBegin>()) {
+      CurrCallExitBeginN = CurrN;
+      CurrentSCtx = CurrN->getStackFrame();
+      FramesModifyingCalculated.insert(CurrentSCtx);
+      // We won't see a change in between two identical exploded nodes: skip.
+      CurrN = CurrN->getFirstPred();
+      continue;
     }
 
-    FramesModifyingCalculated.insert(
-        CurrN->getLocationContext()->getStackFrame());
+    if (auto CE = CurrN->getLocationAs<CallEnter>()) {
+      if (const ExplodedNode *CallExitEndN = getCallExitEnd(CurrCallExitBeginN))
+        if (wasModifiedInFunction(CurrN, CallExitEndN))
+          markFrameAsModifying(CurrentSCtx);
 
-    if (wasModifiedBeforeCallExit(CurrN, LastReturnN)) {
-      const StackFrameContext *SCtx = CurrN->getStackFrame();
-      while (!SCtx->inTopFrame()) {
-        auto p = FramesModifying.insert(SCtx);
-        if (!p.second)
-          break; // Frame and all its parents already inserted.
-        SCtx = SCtx->getParent()->getStackFrame();
+      // We exited this inlined call, lets actualize the stack frame.
+      CurrentSCtx = CurrN->getStackFrame();
+
+      // Stop calculating at the current function, but always regard it as
+      // modifying, so we can avoid notes like this:
+      //   void f(Foo &F) {
+      //     F.field = 0; // note: 0 assigned to 'F.field'
+      //                  // note: returning without writing to 'F.field'
+      //   }
+      if (CE->getCalleeContext() == OriginalSCtx) {
+        markFrameAsModifying(CurrentSCtx);
+        break;
       }
     }
 
-    // Stop calculation at the call to the current function.
-    if (auto CE = CurrN->getLocationAs<CallEnter>())
-      if (CE->getCalleeContext() == OriginalSCtx)
-        break;
+    if (wasModifiedBeforeCallExit(CurrN, CurrCallExitBeginN))
+      markFrameAsModifying(CurrentSCtx);
 
     CurrN = CurrN->getFirstPred();
-  } while (CurrN);
+  }
 }
 
 PathDiagnosticPieceRef NoStateChangeFuncVisitor::VisitNode(
     const ExplodedNode *N, BugReporterContext &BR, PathSensitiveBugReport &R) {
 
   const LocationContext *Ctx = N->getLocationContext();
   const StackFrameContext *SCtx = Ctx->getStackFrame();
   ProgramStateRef State = N->getState();